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

   1 //===----- LegalizeIntegerTypes.cpp - Legalization of integer types -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements integer type expansion and promotion for LegalizeTypes.
  10 // Promotion is the act of changing a computation in an illegal type into a
  11 // computation in a larger type.  For example, implementing i8 arithmetic in an
  12 // i32 register (often needed on powerpc).
  13 // Expansion is the act of changing a computation in an illegal type into a
  14 // computation in two identical registers of a smaller type.  For example,
  15 // implementing i64 arithmetic in two i32 registers (often needed on 32-bit
  16 // targets).
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "LegalizeTypes.h"
  21 #include "llvm/IR/DerivedTypes.h"
  22 #include "llvm/Support/ErrorHandling.h"
  23 #include "llvm/Support/KnownBits.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   LLVM_DEBUG(dbgs() << "Promote integer result: "; N->dump(&DAG);
  39              dbgs() << "\n");
  40   SDValue Res = SDValue();
  41
  42   // See if the target wants to custom expand this node.
  43   if (CustomLowerNode(N, N->getValueType(ResNo), true)) {
  44     LLVM_DEBUG(dbgs() << "Node has been custom expanded, done\n");
  45     return;
  46   }
  47
  48   switch (N->getOpcode()) {
  49   default:
  50 #ifndef NDEBUG
  51     dbgs() << "PromoteIntegerResult #" << ResNo << ": ";
  52     N->dump(&DAG); dbgs() << "\n";
  53 #endif
  54     llvm_unreachable("Do not know how to promote this operator!");
  55   case ISD::MERGE_VALUES:Res = PromoteIntRes_MERGE_VALUES(N, ResNo); break;
  56   case ISD::AssertSext:  Res = PromoteIntRes_AssertSext(N); break;
  57   case ISD::AssertZext:  Res = PromoteIntRes_AssertZext(N); break;
  58   case ISD::BITCAST:     Res = PromoteIntRes_BITCAST(N); break;
  59   case ISD::BITREVERSE:  Res = PromoteIntRes_BITREVERSE(N); break;
  60   case ISD::BSWAP:       Res = PromoteIntRes_BSWAP(N); break;
  61   case ISD::BUILD_PAIR:  Res = PromoteIntRes_BUILD_PAIR(N); break;
  62   case ISD::Constant:    Res = PromoteIntRes_Constant(N); break;
  63   case ISD::CTLZ_ZERO_UNDEF:
  64   case ISD::CTLZ:        Res = PromoteIntRes_CTLZ(N); break;
  65   case ISD::CTPOP:       Res = PromoteIntRes_CTPOP(N); break;
  66   case ISD::CTTZ_ZERO_UNDEF:
  67   case ISD::CTTZ:        Res = PromoteIntRes_CTTZ(N); break;
  68   case ISD::EXTRACT_VECTOR_ELT:
  69                          Res = PromoteIntRes_EXTRACT_VECTOR_ELT(N); break;
  70   case ISD::LOAD:        Res = PromoteIntRes_LOAD(cast<LoadSDNode>(N)); break;
  71   case ISD::MLOAD:       Res = PromoteIntRes_MLOAD(cast<MaskedLoadSDNode>(N));
  72     break;
  73   case ISD::MGATHER:     Res = PromoteIntRes_MGATHER(cast<MaskedGatherSDNode>(N));
  74     break;
  75   case ISD::SELECT:      Res = PromoteIntRes_SELECT(N); break;
  76   case ISD::VSELECT:     Res = PromoteIntRes_VSELECT(N); break;
  77   case ISD::SELECT_CC:   Res = PromoteIntRes_SELECT_CC(N); break;
  78   case ISD::SETCC:       Res = PromoteIntRes_SETCC(N); break;
  79   case ISD::SMIN:
  80   case ISD::SMAX:        Res = PromoteIntRes_SExtIntBinOp(N); break;
  81   case ISD::UMIN:
  82   case ISD::UMAX:        Res = PromoteIntRes_ZExtIntBinOp(N); break;
  83
  84   case ISD::SHL:         Res = PromoteIntRes_SHL(N); break;
  85   case ISD::SIGN_EXTEND_INREG:
  86                          Res = PromoteIntRes_SIGN_EXTEND_INREG(N); break;
  87   case ISD::SRA:         Res = PromoteIntRes_SRA(N); break;
  88   case ISD::SRL:         Res = PromoteIntRes_SRL(N); break;
  89   case ISD::TRUNCATE:    Res = PromoteIntRes_TRUNCATE(N); break;
  90   case ISD::UNDEF:       Res = PromoteIntRes_UNDEF(N); break;
  91   case ISD::VAARG:       Res = PromoteIntRes_VAARG(N); break;
  92
  93   case ISD::EXTRACT_SUBVECTOR:
  94                          Res = PromoteIntRes_EXTRACT_SUBVECTOR(N); break;
  95   case ISD::VECTOR_SHUFFLE:
  96                          Res = PromoteIntRes_VECTOR_SHUFFLE(N); break;
  97   case ISD::INSERT_VECTOR_ELT:
  98                          Res = PromoteIntRes_INSERT_VECTOR_ELT(N); break;
  99   case ISD::BUILD_VECTOR:
 100                          Res = PromoteIntRes_BUILD_VECTOR(N); break;
 101   case ISD::SCALAR_TO_VECTOR:
 102                          Res = PromoteIntRes_SCALAR_TO_VECTOR(N); break;
 103   case ISD::CONCAT_VECTORS:
 104                          Res = PromoteIntRes_CONCAT_VECTORS(N); break;
 105
 106   case ISD::ANY_EXTEND_VECTOR_INREG:
 107   case ISD::SIGN_EXTEND_VECTOR_INREG:
 108   case ISD::ZERO_EXTEND_VECTOR_INREG:
 109                          Res = PromoteIntRes_EXTEND_VECTOR_INREG(N); break;
 110
 111   case ISD::SIGN_EXTEND:
 112   case ISD::ZERO_EXTEND:
 113   case ISD::ANY_EXTEND:  Res = PromoteIntRes_INT_EXTEND(N); break;
 114
 115   case ISD::FP_TO_SINT:
 116   case ISD::FP_TO_UINT:  Res = PromoteIntRes_FP_TO_XINT(N); break;
 117
 118   case ISD::FP_TO_FP16:  Res = PromoteIntRes_FP_TO_FP16(N); break;
 119
 120   case ISD::FLT_ROUNDS_: Res = PromoteIntRes_FLT_ROUNDS(N); break;
 121
 122   case ISD::AND:
 123   case ISD::OR:
 124   case ISD::XOR:
 125   case ISD::ADD:
 126   case ISD::SUB:
 127   case ISD::MUL:         Res = PromoteIntRes_SimpleIntBinOp(N); break;
 128
 129   case ISD::SDIV:
 130   case ISD::SREM:        Res = PromoteIntRes_SExtIntBinOp(N); break;
 131
 132   case ISD::UDIV:
 133   case ISD::UREM:        Res = PromoteIntRes_ZExtIntBinOp(N); break;
 134
 135   case ISD::SADDO:
 136   case ISD::SSUBO:       Res = PromoteIntRes_SADDSUBO(N, ResNo); break;
 137   case ISD::UADDO:
 138   case ISD::USUBO:       Res = PromoteIntRes_UADDSUBO(N, ResNo); break;
 139   case ISD::SMULO:
 140   case ISD::UMULO:       Res = PromoteIntRes_XMULO(N, ResNo); break;
 141
 142   case ISD::ADDE:
 143   case ISD::SUBE:
 144   case ISD::ADDCARRY:
 145   case ISD::SUBCARRY:    Res = PromoteIntRes_ADDSUBCARRY(N, ResNo); break;
 146
 147   case ISD::SADDSAT:
 148   case ISD::UADDSAT:
 149   case ISD::SSUBSAT:
 150   case ISD::USUBSAT:     Res = PromoteIntRes_ADDSUBSAT(N); break;
 151   case ISD::SMULFIX:
 152   case ISD::SMULFIXSAT:
 153   case ISD::UMULFIX:     Res = PromoteIntRes_MULFIX(N); break;
 154   case ISD::ABS:         Res = PromoteIntRes_ABS(N); break;
 155
 156   case ISD::ATOMIC_LOAD:
 157     Res = PromoteIntRes_Atomic0(cast<AtomicSDNode>(N)); break;
 158
 159   case ISD::ATOMIC_LOAD_ADD:
 160   case ISD::ATOMIC_LOAD_SUB:
 161   case ISD::ATOMIC_LOAD_AND:
 162   case ISD::ATOMIC_LOAD_CLR:
 163   case ISD::ATOMIC_LOAD_OR:
 164   case ISD::ATOMIC_LOAD_XOR:
 165   case ISD::ATOMIC_LOAD_NAND:
 166   case ISD::ATOMIC_LOAD_MIN:
 167   case ISD::ATOMIC_LOAD_MAX:
 168   case ISD::ATOMIC_LOAD_UMIN:
 169   case ISD::ATOMIC_LOAD_UMAX:
 170   case ISD::ATOMIC_SWAP:
 171     Res = PromoteIntRes_Atomic1(cast<AtomicSDNode>(N)); break;
 172
 173   case ISD::ATOMIC_CMP_SWAP:
 174   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
 175     Res = PromoteIntRes_AtomicCmpSwap(cast<AtomicSDNode>(N), ResNo);
 176     break;
 177
 178   case ISD::VECREDUCE_ADD:
 179   case ISD::VECREDUCE_MUL:
 180   case ISD::VECREDUCE_AND:
 181   case ISD::VECREDUCE_OR:
 182   case ISD::VECREDUCE_XOR:
 183   case ISD::VECREDUCE_SMAX:
 184   case ISD::VECREDUCE_SMIN:
 185   case ISD::VECREDUCE_UMAX:
 186   case ISD::VECREDUCE_UMIN:
 187     Res = PromoteIntRes_VECREDUCE(N);
 188     break;
 189   }
 190
 191   // If the result is null then the sub-method took care of registering it.
 192   if (Res.getNode())
 193     SetPromotedInteger(SDValue(N, ResNo), Res);
 194 }
 195
 196 SDValue DAGTypeLegalizer::PromoteIntRes_MERGE_VALUES(SDNode *N,
 197                                                      unsigned ResNo) {
 198   SDValue Op = DisintegrateMERGE_VALUES(N, ResNo);
 199   return GetPromotedInteger(Op);
 200 }
 201
 202 SDValue DAGTypeLegalizer::PromoteIntRes_AssertSext(SDNode *N) {
 203   // Sign-extend the new bits, and continue the assertion.
 204   SDValue Op = SExtPromotedInteger(N->getOperand(0));
 205   return DAG.getNode(ISD::AssertSext, SDLoc(N),
 206                      Op.getValueType(), Op, N->getOperand(1));
 207 }
 208
 209 SDValue DAGTypeLegalizer::PromoteIntRes_AssertZext(SDNode *N) {
 210   // Zero the new bits, and continue the assertion.
 211   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
 212   return DAG.getNode(ISD::AssertZext, SDLoc(N),
 213                      Op.getValueType(), Op, N->getOperand(1));
 214 }
 215
 216 SDValue DAGTypeLegalizer::PromoteIntRes_Atomic0(AtomicSDNode *N) {
 217   EVT ResVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 218   SDValue Res = DAG.getAtomic(N->getOpcode(), SDLoc(N),
 219                               N->getMemoryVT(), ResVT,
 220                               N->getChain(), N->getBasePtr(),
 221                               N->getMemOperand());
 222   // Legalize the chain result - switch anything that used the old chain to
 223   // use the new one.
 224   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 225   return Res;
 226 }
 227
 228 SDValue DAGTypeLegalizer::PromoteIntRes_Atomic1(AtomicSDNode *N) {
 229   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
 230   SDValue Res = DAG.getAtomic(N->getOpcode(), SDLoc(N),
 231                               N->getMemoryVT(),
 232                               N->getChain(), N->getBasePtr(),
 233                               Op2, N->getMemOperand());
 234   // Legalize the chain result - switch anything that used the old chain to
 235   // use the new one.
 236   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 237   return Res;
 238 }
 239
 240 SDValue DAGTypeLegalizer::PromoteIntRes_AtomicCmpSwap(AtomicSDNode *N,
 241                                                       unsigned ResNo) {
 242   if (ResNo == 1) {
 243     assert(N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
 244     EVT SVT = getSetCCResultType(N->getOperand(2).getValueType());
 245     EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(1));
 246
 247     // Only use the result of getSetCCResultType if it is legal,
 248     // otherwise just use the promoted result type (NVT).
 249     if (!TLI.isTypeLegal(SVT))
 250       SVT = NVT;
 251
 252     SDVTList VTs = DAG.getVTList(N->getValueType(0), SVT, MVT::Other);
 253     SDValue Res = DAG.getAtomicCmpSwap(
 254         ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS, SDLoc(N), N->getMemoryVT(), VTs,
 255         N->getChain(), N->getBasePtr(), N->getOperand(2), N->getOperand(3),
 256         N->getMemOperand());
 257     ReplaceValueWith(SDValue(N, 0), Res.getValue(0));
 258     ReplaceValueWith(SDValue(N, 2), Res.getValue(2));
 259     return Res.getValue(1);
 260   }
 261
 262   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
 263   SDValue Op3 = GetPromotedInteger(N->getOperand(3));
 264   SDVTList VTs =
 265       DAG.getVTList(Op2.getValueType(), N->getValueType(1), MVT::Other);
 266   SDValue Res = DAG.getAtomicCmpSwap(
 267       N->getOpcode(), SDLoc(N), N->getMemoryVT(), VTs, N->getChain(),
 268       N->getBasePtr(), Op2, Op3, N->getMemOperand());
 269   // Update the use to N with the newly created Res.
 270   for (unsigned i = 1, NumResults = N->getNumValues(); i < NumResults; ++i)
 271     ReplaceValueWith(SDValue(N, i), Res.getValue(i));
 272   return Res;
 273 }
 274
 275 SDValue DAGTypeLegalizer::PromoteIntRes_BITCAST(SDNode *N) {
 276   SDValue InOp = N->getOperand(0);
 277   EVT InVT = InOp.getValueType();
 278   EVT NInVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT);
 279   EVT OutVT = N->getValueType(0);
 280   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
 281   SDLoc dl(N);
 282
 283   switch (getTypeAction(InVT)) {
 284   case TargetLowering::TypeLegal:
 285     break;
 286   case TargetLowering::TypePromoteInteger:
 287     if (NOutVT.bitsEq(NInVT) && !NOutVT.isVector() && !NInVT.isVector())
 288       // The input promotes to the same size.  Convert the promoted value.
 289       return DAG.getNode(ISD::BITCAST, dl, NOutVT, GetPromotedInteger(InOp));
 290     break;
 291   case TargetLowering::TypeSoftenFloat:
 292     // Promote the integer operand by hand.
 293     return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT, GetSoftenedFloat(InOp));
 294   case TargetLowering::TypePromoteFloat: {
 295     // Convert the promoted float by hand.
 296     if (!NOutVT.isVector())
 297       return DAG.getNode(ISD::FP_TO_FP16, dl, NOutVT, GetPromotedFloat(InOp));
 298     break;
 299   }
 300   case TargetLowering::TypeExpandInteger:
 301   case TargetLowering::TypeExpandFloat:
 302     break;
 303   case TargetLowering::TypeScalarizeVector:
 304     // Convert the element to an integer and promote it by hand.
 305     if (!NOutVT.isVector())
 306       return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT,
 307                          BitConvertToInteger(GetScalarizedVector(InOp)));
 308     break;
 309   case TargetLowering::TypeSplitVector: {
 310     if (!NOutVT.isVector()) {
 311       // For example, i32 = BITCAST v2i16 on alpha.  Convert the split
 312       // pieces of the input into integers and reassemble in the final type.
 313       SDValue Lo, Hi;
 314       GetSplitVector(N->getOperand(0), Lo, Hi);
 315       Lo = BitConvertToInteger(Lo);
 316       Hi = BitConvertToInteger(Hi);
 317
 318       if (DAG.getDataLayout().isBigEndian())
 319         std::swap(Lo, Hi);
 320
 321       InOp = DAG.getNode(ISD::ANY_EXTEND, dl,
 322                          EVT::getIntegerVT(*DAG.getContext(),
 323                                            NOutVT.getSizeInBits()),
 324                          JoinIntegers(Lo, Hi));
 325       return DAG.getNode(ISD::BITCAST, dl, NOutVT, InOp);
 326     }
 327     break;
 328   }
 329   case TargetLowering::TypeWidenVector:
 330     // The input is widened to the same size. Convert to the widened value.
 331     // Make sure that the outgoing value is not a vector, because this would
 332     // make us bitcast between two vectors which are legalized in different ways.
 333     if (NOutVT.bitsEq(NInVT) && !NOutVT.isVector())
 334       return DAG.getNode(ISD::BITCAST, dl, NOutVT, GetWidenedVector(InOp));
 335     // If the output type is also a vector and widening it to the same size
 336     // as the widened input type would be a legal type, we can widen the bitcast
 337     // and handle the promotion after.
 338     if (NOutVT.isVector()) {
 339       unsigned WidenInSize = NInVT.getSizeInBits();
 340       unsigned OutSize = OutVT.getSizeInBits();
 341       if (WidenInSize % OutSize == 0) {
 342         unsigned Scale = WidenInSize / OutSize;
 343         EVT WideOutVT = EVT::getVectorVT(*DAG.getContext(),
 344                                          OutVT.getVectorElementType(),
 345                                          OutVT.getVectorNumElements() * Scale);
 346         if (isTypeLegal(WideOutVT)) {
 347           InOp = DAG.getBitcast(WideOutVT, GetWidenedVector(InOp));
 348           MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
 349           InOp = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, OutVT, InOp,
 350                              DAG.getConstant(0, dl, IdxTy));
 351           return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT, InOp);
 352         }
 353       }
 354     }
 355   }
 356
 357   return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT,
 358                      CreateStackStoreLoad(InOp, OutVT));
 359 }
 360
 361 // Helper for BSWAP/BITREVERSE promotion to ensure we can fit the shift amount
 362 // in the VT returned by getShiftAmountTy and to return a safe VT if we can't.
 363 static EVT getShiftAmountTyForConstant(unsigned Val, EVT VT,
 364                                        const TargetLowering &TLI,
 365                                        SelectionDAG &DAG) {
 366   EVT ShiftVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
 367   // If the value won't fit in the prefered type, just use something safe. It
 368   // will be legalized when the shift is expanded.
 369   if ((Log2_32(Val) + 1) > ShiftVT.getScalarSizeInBits())
 370     ShiftVT = MVT::i32;
 371   return ShiftVT;
 372 }
 373
 374 SDValue DAGTypeLegalizer::PromoteIntRes_BSWAP(SDNode *N) {
 375   SDValue Op = GetPromotedInteger(N->getOperand(0));
 376   EVT OVT = N->getValueType(0);
 377   EVT NVT = Op.getValueType();
 378   SDLoc dl(N);
 379
 380   unsigned DiffBits = NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits();
 381   EVT ShiftVT = getShiftAmountTyForConstant(DiffBits, NVT, TLI, DAG);
 382   return DAG.getNode(ISD::SRL, dl, NVT, DAG.getNode(ISD::BSWAP, dl, NVT, Op),
 383                      DAG.getConstant(DiffBits, dl, ShiftVT));
 384 }
 385
 386 SDValue DAGTypeLegalizer::PromoteIntRes_BITREVERSE(SDNode *N) {
 387   SDValue Op = GetPromotedInteger(N->getOperand(0));
 388   EVT OVT = N->getValueType(0);
 389   EVT NVT = Op.getValueType();
 390   SDLoc dl(N);
 391
 392   unsigned DiffBits = NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits();
 393   EVT ShiftVT = getShiftAmountTyForConstant(DiffBits, NVT, TLI, DAG);
 394   return DAG.getNode(ISD::SRL, dl, NVT,
 395                      DAG.getNode(ISD::BITREVERSE, dl, NVT, Op),
 396                      DAG.getConstant(DiffBits, dl, ShiftVT));
 397 }
 398
 399 SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_PAIR(SDNode *N) {
 400   // The pair element type may be legal, or may not promote to the same type as
 401   // the result, for example i14 = BUILD_PAIR (i7, i7).  Handle all cases.
 402   return DAG.getNode(ISD::ANY_EXTEND, SDLoc(N),
 403                      TLI.getTypeToTransformTo(*DAG.getContext(),
 404                      N->getValueType(0)), JoinIntegers(N->getOperand(0),
 405                      N->getOperand(1)));
 406 }
 407
 408 SDValue DAGTypeLegalizer::PromoteIntRes_Constant(SDNode *N) {
 409   EVT VT = N->getValueType(0);
 410   // FIXME there is no actual debug info here
 411   SDLoc dl(N);
 412   // Zero extend things like i1, sign extend everything else.  It shouldn't
 413   // matter in theory which one we pick, but this tends to give better code?
 414   unsigned Opc = VT.isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
 415   SDValue Result = DAG.getNode(Opc, dl,
 416                                TLI.getTypeToTransformTo(*DAG.getContext(), VT),
 417                                SDValue(N, 0));
 418   assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?");
 419   return Result;
 420 }
 421
 422 SDValue DAGTypeLegalizer::PromoteIntRes_CTLZ(SDNode *N) {
 423   // Zero extend to the promoted type and do the count there.
 424   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
 425   SDLoc dl(N);
 426   EVT OVT = N->getValueType(0);
 427   EVT NVT = Op.getValueType();
 428   Op = DAG.getNode(N->getOpcode(), dl, NVT, Op);
 429   // Subtract off the extra leading bits in the bigger type.
 430   return DAG.getNode(
 431       ISD::SUB, dl, NVT, Op,
 432       DAG.getConstant(NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits(), dl,
 433                       NVT));
 434 }
 435
 436 SDValue DAGTypeLegalizer::PromoteIntRes_CTPOP(SDNode *N) {
 437   // Zero extend to the promoted type and do the count there.
 438   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
 439   return DAG.getNode(ISD::CTPOP, SDLoc(N), Op.getValueType(), Op);
 440 }
 441
 442 SDValue DAGTypeLegalizer::PromoteIntRes_CTTZ(SDNode *N) {
 443   SDValue Op = GetPromotedInteger(N->getOperand(0));
 444   EVT OVT = N->getValueType(0);
 445   EVT NVT = Op.getValueType();
 446   SDLoc dl(N);
 447   if (N->getOpcode() == ISD::CTTZ) {
 448     // The count is the same in the promoted type except if the original
 449     // value was zero.  This can be handled by setting the bit just off
 450     // the top of the original type.
 451     auto TopBit = APInt::getOneBitSet(NVT.getScalarSizeInBits(),
 452                                       OVT.getScalarSizeInBits());
 453     Op = DAG.getNode(ISD::OR, dl, NVT, Op, DAG.getConstant(TopBit, dl, NVT));
 454   }
 455   return DAG.getNode(N->getOpcode(), dl, NVT, Op);
 456 }
 457
 458 SDValue DAGTypeLegalizer::PromoteIntRes_EXTRACT_VECTOR_ELT(SDNode *N) {
 459   SDLoc dl(N);
 460   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 461
 462   SDValue Op0 = N->getOperand(0);
 463   SDValue Op1 = N->getOperand(1);
 464
 465   // If the input also needs to be promoted, do that first so we can get a
 466   // get a good idea for the output type.
 467   if (TLI.getTypeAction(*DAG.getContext(), Op0.getValueType())
 468       == TargetLowering::TypePromoteInteger) {
 469     SDValue In = GetPromotedInteger(Op0);
 470
 471     // If the new type is larger than NVT, use it. We probably won't need to
 472     // promote it again.
 473     EVT SVT = In.getValueType().getScalarType();
 474     if (SVT.bitsGE(NVT)) {
 475       SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, SVT, In, Op1);
 476       return DAG.getAnyExtOrTrunc(Ext, dl, NVT);
 477     }
 478   }
 479
 480   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, NVT, Op0, Op1);
 481 }
 482
 483 SDValue DAGTypeLegalizer::PromoteIntRes_FP_TO_XINT(SDNode *N) {
 484   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 485   unsigned NewOpc = N->getOpcode();
 486   SDLoc dl(N);
 487
 488   // If we're promoting a UINT to a larger size and the larger FP_TO_UINT is
 489   // not Legal, check to see if we can use FP_TO_SINT instead.  (If both UINT
 490   // and SINT conversions are Custom, there is no way to tell which is
 491   // preferable. We choose SINT because that's the right thing on PPC.)
 492   if (N->getOpcode() == ISD::FP_TO_UINT &&
 493       !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
 494       TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NVT))
 495     NewOpc = ISD::FP_TO_SINT;
 496
 497   SDValue Res = DAG.getNode(NewOpc, dl, NVT, N->getOperand(0));
 498
 499   // Assert that the converted value fits in the original type.  If it doesn't
 500   // (eg: because the value being converted is too big), then the result of the
 501   // original operation was undefined anyway, so the assert is still correct.
 502   //
 503   // NOTE: fp-to-uint to fp-to-sint promotion guarantees zero extend. For example:
 504   //   before legalization: fp-to-uint16, 65534. -> 0xfffe
 505   //   after legalization: fp-to-sint32, 65534. -> 0x0000fffe
 506   return DAG.getNode(N->getOpcode() == ISD::FP_TO_UINT ?
 507                      ISD::AssertZext : ISD::AssertSext, dl, NVT, Res,
 508                      DAG.getValueType(N->getValueType(0).getScalarType()));
 509 }
 510
 511 SDValue DAGTypeLegalizer::PromoteIntRes_FP_TO_FP16(SDNode *N) {
 512   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 513   SDLoc dl(N);
 514
 515   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
 516 }
 517
 518 SDValue DAGTypeLegalizer::PromoteIntRes_FLT_ROUNDS(SDNode *N) {
 519   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 520   SDLoc dl(N);
 521
 522   return DAG.getNode(N->getOpcode(), dl, NVT);
 523 }
 524
 525 SDValue DAGTypeLegalizer::PromoteIntRes_INT_EXTEND(SDNode *N) {
 526   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 527   SDLoc dl(N);
 528
 529   if (getTypeAction(N->getOperand(0).getValueType())
 530       == TargetLowering::TypePromoteInteger) {
 531     SDValue Res = GetPromotedInteger(N->getOperand(0));
 532     assert(Res.getValueType().bitsLE(NVT) && "Extension doesn't make sense!");
 533
 534     // If the result and operand types are the same after promotion, simplify
 535     // to an in-register extension.
 536     if (NVT == Res.getValueType()) {
 537       // The high bits are not guaranteed to be anything.  Insert an extend.
 538       if (N->getOpcode() == ISD::SIGN_EXTEND)
 539         return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NVT, Res,
 540                            DAG.getValueType(N->getOperand(0).getValueType()));
 541       if (N->getOpcode() == ISD::ZERO_EXTEND)
 542         return DAG.getZeroExtendInReg(Res, dl,
 543                       N->getOperand(0).getValueType().getScalarType());
 544       assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!");
 545       return Res;
 546     }
 547   }
 548
 549   // Otherwise, just extend the original operand all the way to the larger type.
 550   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
 551 }
 552
 553 SDValue DAGTypeLegalizer::PromoteIntRes_LOAD(LoadSDNode *N) {
 554   assert(ISD::isUNINDEXEDLoad(N) && "Indexed load during type legalization!");
 555   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 556   ISD::LoadExtType ExtType =
 557     ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType();
 558   SDLoc dl(N);
 559   SDValue Res = DAG.getExtLoad(ExtType, dl, NVT, N->getChain(), N->getBasePtr(),
 560                                N->getMemoryVT(), N->getMemOperand());
 561
 562   // Legalize the chain result - switch anything that used the old chain to
 563   // use the new one.
 564   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 565   return Res;
 566 }
 567
 568 SDValue DAGTypeLegalizer::PromoteIntRes_MLOAD(MaskedLoadSDNode *N) {
 569   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 570   SDValue ExtPassThru = GetPromotedInteger(N->getPassThru());
 571
 572   SDLoc dl(N);
 573   SDValue Res = DAG.getMaskedLoad(NVT, dl, N->getChain(), N->getBasePtr(),
 574                                   N->getMask(), ExtPassThru, N->getMemoryVT(),
 575                                   N->getMemOperand(), ISD::EXTLOAD);
 576   // Legalize the chain result - switch anything that used the old chain to
 577   // use the new one.
 578   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 579   return Res;
 580 }
 581
 582 SDValue DAGTypeLegalizer::PromoteIntRes_MGATHER(MaskedGatherSDNode *N) {
 583   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 584   SDValue ExtPassThru = GetPromotedInteger(N->getPassThru());
 585   assert(NVT == ExtPassThru.getValueType() &&
 586       "Gather result type and the passThru agrument type should be the same");
 587
 588   SDLoc dl(N);
 589   SDValue Ops[] = {N->getChain(), ExtPassThru, N->getMask(), N->getBasePtr(),
 590                    N->getIndex(), N->getScale() };
 591   SDValue Res = DAG.getMaskedGather(DAG.getVTList(NVT, MVT::Other),
 592                                     N->getMemoryVT(), dl, Ops,
 593                                     N->getMemOperand());
 594   // Legalize the chain result - switch anything that used the old chain to
 595   // use the new one.
 596   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 597   return Res;
 598 }
 599
 600 /// Promote the overflow flag of an overflowing arithmetic node.
 601 SDValue DAGTypeLegalizer::PromoteIntRes_Overflow(SDNode *N) {
 602   // Change the return type of the boolean result while obeying
 603   // getSetCCResultType.
 604   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(1));
 605   EVT VT = N->getValueType(0);
 606   EVT SVT = getSetCCResultType(VT);
 607   SDValue Ops[3] = { N->getOperand(0), N->getOperand(1) };
 608   unsigned NumOps = N->getNumOperands();
 609   assert(NumOps <= 3 && "Too many operands");
 610   if (NumOps == 3)
 611     Ops[2] = N->getOperand(2);
 612
 613   SDLoc dl(N);
 614   SDValue Res = DAG.getNode(N->getOpcode(), dl, DAG.getVTList(VT, SVT),
 615                             makeArrayRef(Ops, NumOps));
 616
 617   // Modified the sum result - switch anything that used the old sum to use
 618   // the new one.
 619   ReplaceValueWith(SDValue(N, 0), Res);
 620
 621   // Convert to the expected type.
 622   return DAG.getBoolExtOrTrunc(Res.getValue(1), dl, NVT, VT);
 623 }
 624
 625 SDValue DAGTypeLegalizer::PromoteIntRes_ADDSUBSAT(SDNode *N) {
 626   // For promoting iN -> iM, this can be expanded by
 627   // 1. ANY_EXTEND iN to iM
 628   // 2. SHL by M-N
 629   // 3. [US][ADD|SUB]SAT
 630   // 4. L/ASHR by M-N
 631   SDLoc dl(N);
 632   SDValue Op1 = N->getOperand(0);
 633   SDValue Op2 = N->getOperand(1);
 634   unsigned OldBits = Op1.getScalarValueSizeInBits();
 635
 636   unsigned Opcode = N->getOpcode();
 637   unsigned ShiftOp;
 638   switch (Opcode) {
 639   case ISD::SADDSAT:
 640   case ISD::SSUBSAT:
 641     ShiftOp = ISD::SRA;
 642     break;
 643   case ISD::UADDSAT:
 644   case ISD::USUBSAT:
 645     ShiftOp = ISD::SRL;
 646     break;
 647   default:
 648     llvm_unreachable("Expected opcode to be signed or unsigned saturation "
 649                      "addition or subtraction");
 650   }
 651
 652   SDValue Op1Promoted = GetPromotedInteger(Op1);
 653   SDValue Op2Promoted = GetPromotedInteger(Op2);
 654
 655   EVT PromotedType = Op1Promoted.getValueType();
 656   unsigned NewBits = PromotedType.getScalarSizeInBits();
 657   unsigned SHLAmount = NewBits - OldBits;
 658   EVT SHVT = TLI.getShiftAmountTy(PromotedType, DAG.getDataLayout());
 659   SDValue ShiftAmount = DAG.getConstant(SHLAmount, dl, SHVT);
 660   Op1Promoted =
 661       DAG.getNode(ISD::SHL, dl, PromotedType, Op1Promoted, ShiftAmount);
 662   Op2Promoted =
 663       DAG.getNode(ISD::SHL, dl, PromotedType, Op2Promoted, ShiftAmount);
 664
 665   SDValue Result =
 666       DAG.getNode(Opcode, dl, PromotedType, Op1Promoted, Op2Promoted);
 667   return DAG.getNode(ShiftOp, dl, PromotedType, Result, ShiftAmount);
 668 }
 669
 670 SDValue DAGTypeLegalizer::PromoteIntRes_MULFIX(SDNode *N) {
 671   // Can just promote the operands then continue with operation.
 672   SDLoc dl(N);
 673   SDValue Op1Promoted, Op2Promoted;
 674   bool Signed =
 675       N->getOpcode() == ISD::SMULFIX || N->getOpcode() == ISD::SMULFIXSAT;
 676   if (Signed) {
 677     Op1Promoted = SExtPromotedInteger(N->getOperand(0));
 678     Op2Promoted = SExtPromotedInteger(N->getOperand(1));
 679   } else {
 680     Op1Promoted = ZExtPromotedInteger(N->getOperand(0));
 681     Op2Promoted = ZExtPromotedInteger(N->getOperand(1));
 682   }
 683   EVT OldType = N->getOperand(0).getValueType();
 684   EVT PromotedType = Op1Promoted.getValueType();
 685   unsigned DiffSize =
 686       PromotedType.getScalarSizeInBits() - OldType.getScalarSizeInBits();
 687
 688   bool Saturating = N->getOpcode() == ISD::SMULFIXSAT;
 689   if (Saturating) {
 690     // Promoting the operand and result values changes the saturation width,
 691     // which is extends the values that we clamp to on saturation. This could be
 692     // resolved by shifting one of the operands the same amount, which would
 693     // also shift the result we compare against, then shifting back.
 694     EVT ShiftTy = TLI.getShiftAmountTy(PromotedType, DAG.getDataLayout());
 695     Op1Promoted = DAG.getNode(ISD::SHL, dl, PromotedType, Op1Promoted,
 696                               DAG.getConstant(DiffSize, dl, ShiftTy));
 697     SDValue Result = DAG.getNode(N->getOpcode(), dl, PromotedType, Op1Promoted,
 698                                  Op2Promoted, N->getOperand(2));
 699     unsigned ShiftOp = Signed ? ISD::SRA : ISD::SRL;
 700     return DAG.getNode(ShiftOp, dl, PromotedType, Result,
 701                        DAG.getConstant(DiffSize, dl, ShiftTy));
 702   }
 703   return DAG.getNode(N->getOpcode(), dl, PromotedType, Op1Promoted, Op2Promoted,
 704                      N->getOperand(2));
 705 }
 706
 707 SDValue DAGTypeLegalizer::PromoteIntRes_SADDSUBO(SDNode *N, unsigned ResNo) {
 708   if (ResNo == 1)
 709     return PromoteIntRes_Overflow(N);
 710
 711   // The operation overflowed iff the result in the larger type is not the
 712   // sign extension of its truncation to the original type.
 713   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
 714   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
 715   EVT OVT = N->getOperand(0).getValueType();
 716   EVT NVT = LHS.getValueType();
 717   SDLoc dl(N);
 718
 719   // Do the arithmetic in the larger type.
 720   unsigned Opcode = N->getOpcode() == ISD::SADDO ? ISD::ADD : ISD::SUB;
 721   SDValue Res = DAG.getNode(Opcode, dl, NVT, LHS, RHS);
 722
 723   // Calculate the overflow flag: sign extend the arithmetic result from
 724   // the original type.
 725   SDValue Ofl = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NVT, Res,
 726                             DAG.getValueType(OVT));
 727   // Overflowed if and only if this is not equal to Res.
 728   Ofl = DAG.getSetCC(dl, N->getValueType(1), Ofl, Res, ISD::SETNE);
 729
 730   // Use the calculated overflow everywhere.
 731   ReplaceValueWith(SDValue(N, 1), Ofl);
 732
 733   return Res;
 734 }
 735
 736 SDValue DAGTypeLegalizer::PromoteIntRes_SELECT(SDNode *N) {
 737   SDValue LHS = GetPromotedInteger(N->getOperand(1));
 738   SDValue RHS = GetPromotedInteger(N->getOperand(2));
 739   return DAG.getSelect(SDLoc(N),
 740                        LHS.getValueType(), N->getOperand(0), LHS, RHS);
 741 }
 742
 743 SDValue DAGTypeLegalizer::PromoteIntRes_VSELECT(SDNode *N) {
 744   SDValue Mask = N->getOperand(0);
 745
 746   SDValue LHS = GetPromotedInteger(N->getOperand(1));
 747   SDValue RHS = GetPromotedInteger(N->getOperand(2));
 748   return DAG.getNode(ISD::VSELECT, SDLoc(N),
 749                      LHS.getValueType(), Mask, LHS, RHS);
 750 }
 751
 752 SDValue DAGTypeLegalizer::PromoteIntRes_SELECT_CC(SDNode *N) {
 753   SDValue LHS = GetPromotedInteger(N->getOperand(2));
 754   SDValue RHS = GetPromotedInteger(N->getOperand(3));
 755   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
 756                      LHS.getValueType(), N->getOperand(0),
 757                      N->getOperand(1), LHS, RHS, N->getOperand(4));
 758 }
 759
 760 SDValue DAGTypeLegalizer::PromoteIntRes_SETCC(SDNode *N) {
 761   EVT InVT = N->getOperand(0).getValueType();
 762   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 763
 764   EVT SVT = getSetCCResultType(InVT);
 765
 766   // If we got back a type that needs to be promoted, this likely means the
 767   // the input type also needs to be promoted. So get the promoted type for
 768   // the input and try the query again.
 769   if (getTypeAction(SVT) == TargetLowering::TypePromoteInteger) {
 770     if (getTypeAction(InVT) == TargetLowering::TypePromoteInteger) {
 771       InVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT);
 772       SVT = getSetCCResultType(InVT);
 773     } else {
 774       // Input type isn't promoted, just use the default promoted type.
 775       SVT = NVT;
 776     }
 777   }
 778
 779   SDLoc dl(N);
 780   assert(SVT.isVector() == N->getOperand(0).getValueType().isVector() &&
 781          "Vector compare must return a vector result!");
 782
 783   // Get the SETCC result using the canonical SETCC type.
 784   SDValue SetCC = DAG.getNode(N->getOpcode(), dl, SVT, N->getOperand(0),
 785                               N->getOperand(1), N->getOperand(2));
 786
 787   // Convert to the expected type.
 788   return DAG.getSExtOrTrunc(SetCC, dl, NVT);
 789 }
 790
 791 SDValue DAGTypeLegalizer::PromoteIntRes_SHL(SDNode *N) {
 792   SDValue LHS = GetPromotedInteger(N->getOperand(0));
 793   SDValue RHS = N->getOperand(1);
 794   if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger)
 795     RHS = ZExtPromotedInteger(RHS);
 796   return DAG.getNode(ISD::SHL, SDLoc(N), LHS.getValueType(), LHS, RHS);
 797 }
 798
 799 SDValue DAGTypeLegalizer::PromoteIntRes_SIGN_EXTEND_INREG(SDNode *N) {
 800   SDValue Op = GetPromotedInteger(N->getOperand(0));
 801   return DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N),
 802                      Op.getValueType(), Op, N->getOperand(1));
 803 }
 804
 805 SDValue DAGTypeLegalizer::PromoteIntRes_SimpleIntBinOp(SDNode *N) {
 806   // The input may have strange things in the top bits of the registers, but
 807   // these operations don't care.  They may have weird bits going out, but
 808   // that too is okay if they are integer operations.
 809   SDValue LHS = GetPromotedInteger(N->getOperand(0));
 810   SDValue RHS = GetPromotedInteger(N->getOperand(1));
 811   return DAG.getNode(N->getOpcode(), SDLoc(N),
 812                      LHS.getValueType(), LHS, RHS);
 813 }
 814
 815 SDValue DAGTypeLegalizer::PromoteIntRes_SExtIntBinOp(SDNode *N) {
 816   // Sign extend the input.
 817   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
 818   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
 819   return DAG.getNode(N->getOpcode(), SDLoc(N),
 820                      LHS.getValueType(), LHS, RHS);
 821 }
 822
 823 SDValue DAGTypeLegalizer::PromoteIntRes_ZExtIntBinOp(SDNode *N) {
 824   // Zero extend the input.
 825   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
 826   SDValue RHS = ZExtPromotedInteger(N->getOperand(1));
 827   return DAG.getNode(N->getOpcode(), SDLoc(N),
 828                      LHS.getValueType(), LHS, RHS);
 829 }
 830
 831 SDValue DAGTypeLegalizer::PromoteIntRes_SRA(SDNode *N) {
 832   // The input value must be properly sign extended.
 833   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
 834   SDValue RHS = N->getOperand(1);
 835   if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger)
 836     RHS = ZExtPromotedInteger(RHS);
 837   return DAG.getNode(ISD::SRA, SDLoc(N), LHS.getValueType(), LHS, RHS);
 838 }
 839
 840 SDValue DAGTypeLegalizer::PromoteIntRes_SRL(SDNode *N) {
 841   // The input value must be properly zero extended.
 842   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
 843   SDValue RHS = N->getOperand(1);
 844   if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger)
 845     RHS = ZExtPromotedInteger(RHS);
 846   return DAG.getNode(ISD::SRL, SDLoc(N), LHS.getValueType(), LHS, RHS);
 847 }
 848
 849 SDValue DAGTypeLegalizer::PromoteIntRes_TRUNCATE(SDNode *N) {
 850   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 851   SDValue Res;
 852   SDValue InOp = N->getOperand(0);
 853   SDLoc dl(N);
 854
 855   switch (getTypeAction(InOp.getValueType())) {
 856   default: llvm_unreachable("Unknown type action!");
 857   case TargetLowering::TypeLegal:
 858   case TargetLowering::TypeExpandInteger:
 859     Res = InOp;
 860     break;
 861   case TargetLowering::TypePromoteInteger:
 862     Res = GetPromotedInteger(InOp);
 863     break;
 864   case TargetLowering::TypeSplitVector: {
 865     EVT InVT = InOp.getValueType();
 866     assert(InVT.isVector() && "Cannot split scalar types");
 867     unsigned NumElts = InVT.getVectorNumElements();
 868     assert(NumElts == NVT.getVectorNumElements() &&
 869            "Dst and Src must have the same number of elements");
 870     assert(isPowerOf2_32(NumElts) &&
 871            "Promoted vector type must be a power of two");
 872
 873     SDValue EOp1, EOp2;
 874     GetSplitVector(InOp, EOp1, EOp2);
 875
 876     EVT HalfNVT = EVT::getVectorVT(*DAG.getContext(), NVT.getScalarType(),
 877                                    NumElts/2);
 878     EOp1 = DAG.getNode(ISD::TRUNCATE, dl, HalfNVT, EOp1);
 879     EOp2 = DAG.getNode(ISD::TRUNCATE, dl, HalfNVT, EOp2);
 880
 881     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, EOp1, EOp2);
 882   }
 883   case TargetLowering::TypeWidenVector: {
 884     SDValue WideInOp = GetWidenedVector(InOp);
 885
 886     // Truncate widened InOp.
 887     unsigned NumElem = WideInOp.getValueType().getVectorNumElements();
 888     EVT TruncVT = EVT::getVectorVT(*DAG.getContext(),
 889                                    N->getValueType(0).getScalarType(), NumElem);
 890     SDValue WideTrunc = DAG.getNode(ISD::TRUNCATE, dl, TruncVT, WideInOp);
 891
 892     // Zero extend so that the elements are of same type as those of NVT
 893     EVT ExtVT = EVT::getVectorVT(*DAG.getContext(), NVT.getVectorElementType(),
 894                                  NumElem);
 895     SDValue WideExt = DAG.getNode(ISD::ZERO_EXTEND, dl, ExtVT, WideTrunc);
 896
 897     // Extract the low NVT subvector.
 898     MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
 899     SDValue ZeroIdx = DAG.getConstant(0, dl, IdxTy);
 900     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, NVT, WideExt, ZeroIdx);
 901   }
 902   }
 903
 904   // Truncate to NVT instead of VT
 905   return DAG.getNode(ISD::TRUNCATE, dl, NVT, Res);
 906 }
 907
 908 SDValue DAGTypeLegalizer::PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo) {
 909   if (ResNo == 1)
 910     return PromoteIntRes_Overflow(N);
 911
 912   // The operation overflowed iff the result in the larger type is not the
 913   // zero extension of its truncation to the original type.
 914   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
 915   SDValue RHS = ZExtPromotedInteger(N->getOperand(1));
 916   EVT OVT = N->getOperand(0).getValueType();
 917   EVT NVT = LHS.getValueType();
 918   SDLoc dl(N);
 919
 920   // Do the arithmetic in the larger type.
 921   unsigned Opcode = N->getOpcode() == ISD::UADDO ? ISD::ADD : ISD::SUB;
 922   SDValue Res = DAG.getNode(Opcode, dl, NVT, LHS, RHS);
 923
 924   // Calculate the overflow flag: zero extend the arithmetic result from
 925   // the original type.
 926   SDValue Ofl = DAG.getZeroExtendInReg(Res, dl, OVT.getScalarType());
 927   // Overflowed if and only if this is not equal to Res.
 928   Ofl = DAG.getSetCC(dl, N->getValueType(1), Ofl, Res, ISD::SETNE);
 929
 930   // Use the calculated overflow everywhere.
 931   ReplaceValueWith(SDValue(N, 1), Ofl);
 932
 933   return Res;
 934 }
 935
 936 // Handle promotion for the ADDE/SUBE/ADDCARRY/SUBCARRY nodes. Notice that
 937 // the third operand of ADDE/SUBE nodes is carry flag, which differs from
 938 // the ADDCARRY/SUBCARRY nodes in that the third operand is carry Boolean.
 939 SDValue DAGTypeLegalizer::PromoteIntRes_ADDSUBCARRY(SDNode *N, unsigned ResNo) {
 940   if (ResNo == 1)
 941     return PromoteIntRes_Overflow(N);
 942
 943   // We need to sign-extend the operands so the carry value computed by the
 944   // wide operation will be equivalent to the carry value computed by the
 945   // narrow operation.
 946   // An ADDCARRY can generate carry only if any of the operands has its
 947   // most significant bit set. Sign extension propagates the most significant
 948   // bit into the higher bits which means the extra bit that the narrow
 949   // addition would need (i.e. the carry) will be propagated through the higher
 950   // bits of the wide addition.
 951   // A SUBCARRY can generate borrow only if LHS < RHS and this property will be
 952   // preserved by sign extension.
 953   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
 954   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
 955
 956   EVT ValueVTs[] = {LHS.getValueType(), N->getValueType(1)};
 957
 958   // Do the arithmetic in the wide type.
 959   SDValue Res = DAG.getNode(N->getOpcode(), SDLoc(N), DAG.getVTList(ValueVTs),
 960                             LHS, RHS, N->getOperand(2));
 961
 962   // Update the users of the original carry/borrow value.
 963   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 964
 965   return SDValue(Res.getNode(), 0);
 966 }
 967
 968 SDValue DAGTypeLegalizer::PromoteIntRes_ABS(SDNode *N) {
 969   SDValue Op0 = SExtPromotedInteger(N->getOperand(0));
 970   return DAG.getNode(ISD::ABS, SDLoc(N), Op0.getValueType(), Op0);
 971 }
 972
 973 SDValue DAGTypeLegalizer::PromoteIntRes_XMULO(SDNode *N, unsigned ResNo) {
 974   // Promote the overflow bit trivially.
 975   if (ResNo == 1)
 976     return PromoteIntRes_Overflow(N);
 977
 978   SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);
 979   SDLoc DL(N);
 980   EVT SmallVT = LHS.getValueType();
 981
 982   // To determine if the result overflowed in a larger type, we extend the
 983   // input to the larger type, do the multiply (checking if it overflows),
 984   // then also check the high bits of the result to see if overflow happened
 985   // there.
 986   if (N->getOpcode() == ISD::SMULO) {
 987     LHS = SExtPromotedInteger(LHS);
 988     RHS = SExtPromotedInteger(RHS);
 989   } else {
 990     LHS = ZExtPromotedInteger(LHS);
 991     RHS = ZExtPromotedInteger(RHS);
 992   }
 993   SDVTList VTs = DAG.getVTList(LHS.getValueType(), N->getValueType(1));
 994   SDValue Mul = DAG.getNode(N->getOpcode(), DL, VTs, LHS, RHS);
 995
 996   // Overflow occurred if it occurred in the larger type, or if the high part
 997   // of the result does not zero/sign-extend the low part.  Check this second
 998   // possibility first.
 999   SDValue Overflow;
1000   if (N->getOpcode() == ISD::UMULO) {
1001     // Unsigned overflow occurred if the high part is non-zero.
1002     unsigned Shift = SmallVT.getScalarSizeInBits();
1003     EVT ShiftTy = getShiftAmountTyForConstant(Shift, Mul.getValueType(),
1004                                               TLI, DAG);
1005     SDValue Hi = DAG.getNode(ISD::SRL, DL, Mul.getValueType(), Mul,
1006                              DAG.getConstant(Shift, DL, ShiftTy));
1007     Overflow = DAG.getSetCC(DL, N->getValueType(1), Hi,
1008                             DAG.getConstant(0, DL, Hi.getValueType()),
1009                             ISD::SETNE);
1010   } else {
1011     // Signed overflow occurred if the high part does not sign extend the low.
1012     SDValue SExt = DAG.getNode(ISD::SIGN_EXTEND_INREG, DL, Mul.getValueType(),
1013                                Mul, DAG.getValueType(SmallVT));
1014     Overflow = DAG.getSetCC(DL, N->getValueType(1), SExt, Mul, ISD::SETNE);
1015   }
1016
1017   // The only other way for overflow to occur is if the multiplication in the
1018   // larger type itself overflowed.
1019   Overflow = DAG.getNode(ISD::OR, DL, N->getValueType(1), Overflow,
1020                          SDValue(Mul.getNode(), 1));
1021
1022   // Use the calculated overflow everywhere.
1023   ReplaceValueWith(SDValue(N, 1), Overflow);
1024   return Mul;
1025 }
1026
1027 SDValue DAGTypeLegalizer::PromoteIntRes_UNDEF(SDNode *N) {
1028   return DAG.getUNDEF(TLI.getTypeToTransformTo(*DAG.getContext(),
1029                                                N->getValueType(0)));
1030 }
1031
1032 SDValue DAGTypeLegalizer::PromoteIntRes_VAARG(SDNode *N) {
1033   SDValue Chain = N->getOperand(0); // Get the chain.
1034   SDValue Ptr = N->getOperand(1); // Get the pointer.
1035   EVT VT = N->getValueType(0);
1036   SDLoc dl(N);
1037
1038   MVT RegVT = TLI.getRegisterType(*DAG.getContext(), VT);
1039   unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), VT);
1040   // The argument is passed as NumRegs registers of type RegVT.
1041
1042   SmallVector<SDValue, 8> Parts(NumRegs);
1043   for (unsigned i = 0; i < NumRegs; ++i) {
1044     Parts[i] = DAG.getVAArg(RegVT, dl, Chain, Ptr, N->getOperand(2),
1045                             N->getConstantOperandVal(3));
1046     Chain = Parts[i].getValue(1);
1047   }
1048
1049   // Handle endianness of the load.
1050   if (DAG.getDataLayout().isBigEndian())
1051     std::reverse(Parts.begin(), Parts.end());
1052
1053   // Assemble the parts in the promoted type.
1054   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1055   SDValue Res = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Parts[0]);
1056   for (unsigned i = 1; i < NumRegs; ++i) {
1057     SDValue Part = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Parts[i]);
1058     // Shift it to the right position and "or" it in.
1059     Part = DAG.getNode(ISD::SHL, dl, NVT, Part,
1060                        DAG.getConstant(i * RegVT.getSizeInBits(), dl,
1061                                        TLI.getPointerTy(DAG.getDataLayout())));
1062     Res = DAG.getNode(ISD::OR, dl, NVT, Res, Part);
1063   }
1064
1065   // Modified the chain result - switch anything that used the old chain to
1066   // use the new one.
1067   ReplaceValueWith(SDValue(N, 1), Chain);
1068
1069   return Res;
1070 }
1071
1072 //===----------------------------------------------------------------------===//
1073 //  Integer Operand Promotion
1074 //===----------------------------------------------------------------------===//
1075
1076 /// PromoteIntegerOperand - This method is called when the specified operand of
1077 /// the specified node is found to need promotion.  At this point, all of the
1078 /// result types of the node are known to be legal, but other operands of the
1079 /// node may need promotion or expansion as well as the specified one.
1080 bool DAGTypeLegalizer::PromoteIntegerOperand(SDNode *N, unsigned OpNo) {
1081   LLVM_DEBUG(dbgs() << "Promote integer operand: "; N->dump(&DAG);
1082              dbgs() << "\n");
1083   SDValue Res = SDValue();
1084
1085   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false)) {
1086     LLVM_DEBUG(dbgs() << "Node has been custom lowered, done\n");
1087     return false;
1088   }
1089
1090   switch (N->getOpcode()) {
1091     default:
1092   #ifndef NDEBUG
1093     dbgs() << "PromoteIntegerOperand Op #" << OpNo << ": ";
1094     N->dump(&DAG); dbgs() << "\n";
1095   #endif
1096     llvm_unreachable("Do not know how to promote this operator's operand!");
1097
1098   case ISD::ANY_EXTEND:   Res = PromoteIntOp_ANY_EXTEND(N); break;
1099   case ISD::ATOMIC_STORE:
1100     Res = PromoteIntOp_ATOMIC_STORE(cast<AtomicSDNode>(N));
1101     break;
1102   case ISD::BITCAST:      Res = PromoteIntOp_BITCAST(N); break;
1103   case ISD::BR_CC:        Res = PromoteIntOp_BR_CC(N, OpNo); break;
1104   case ISD::BRCOND:       Res = PromoteIntOp_BRCOND(N, OpNo); break;
1105   case ISD::BUILD_PAIR:   Res = PromoteIntOp_BUILD_PAIR(N); break;
1106   case ISD::BUILD_VECTOR: Res = PromoteIntOp_BUILD_VECTOR(N); break;
1107   case ISD::CONCAT_VECTORS: Res = PromoteIntOp_CONCAT_VECTORS(N); break;
1108   case ISD::EXTRACT_VECTOR_ELT: Res = PromoteIntOp_EXTRACT_VECTOR_ELT(N); break;
1109   case ISD::INSERT_VECTOR_ELT:
1110                           Res = PromoteIntOp_INSERT_VECTOR_ELT(N, OpNo);break;
1111   case ISD::SCALAR_TO_VECTOR:
1112                           Res = PromoteIntOp_SCALAR_TO_VECTOR(N); break;
1113   case ISD::VSELECT:
1114   case ISD::SELECT:       Res = PromoteIntOp_SELECT(N, OpNo); break;
1115   case ISD::SELECT_CC:    Res = PromoteIntOp_SELECT_CC(N, OpNo); break;
1116   case ISD::SETCC:        Res = PromoteIntOp_SETCC(N, OpNo); break;
1117   case ISD::SIGN_EXTEND:  Res = PromoteIntOp_SIGN_EXTEND(N); break;
1118   case ISD::SINT_TO_FP:   Res = PromoteIntOp_SINT_TO_FP(N); break;
1119   case ISD::STORE:        Res = PromoteIntOp_STORE(cast<StoreSDNode>(N),
1120                                                    OpNo); break;
1121   case ISD::MSTORE:       Res = PromoteIntOp_MSTORE(cast<MaskedStoreSDNode>(N),
1122                                                     OpNo); break;
1123   case ISD::MLOAD:        Res = PromoteIntOp_MLOAD(cast<MaskedLoadSDNode>(N),
1124                                                     OpNo); break;
1125   case ISD::MGATHER:  Res = PromoteIntOp_MGATHER(cast<MaskedGatherSDNode>(N),
1126                                                  OpNo); break;
1127   case ISD::MSCATTER: Res = PromoteIntOp_MSCATTER(cast<MaskedScatterSDNode>(N),
1128                                                   OpNo); break;
1129   case ISD::TRUNCATE:     Res = PromoteIntOp_TRUNCATE(N); break;
1130   case ISD::FP16_TO_FP:
1131   case ISD::UINT_TO_FP:   Res = PromoteIntOp_UINT_TO_FP(N); break;
1132   case ISD::ZERO_EXTEND:  Res = PromoteIntOp_ZERO_EXTEND(N); break;
1133   case ISD::EXTRACT_SUBVECTOR: Res = PromoteIntOp_EXTRACT_SUBVECTOR(N); break;
1134
1135   case ISD::SHL:
1136   case ISD::SRA:
1137   case ISD::SRL:
1138   case ISD::ROTL:
1139   case ISD::ROTR: Res = PromoteIntOp_Shift(N); break;
1140
1141   case ISD::ADDCARRY:
1142   case ISD::SUBCARRY: Res = PromoteIntOp_ADDSUBCARRY(N, OpNo); break;
1143
1144   case ISD::FRAMEADDR:
1145   case ISD::RETURNADDR: Res = PromoteIntOp_FRAMERETURNADDR(N); break;
1146
1147   case ISD::PREFETCH: Res = PromoteIntOp_PREFETCH(N, OpNo); break;
1148
1149   case ISD::SMULFIX:
1150   case ISD::SMULFIXSAT:
1151   case ISD::UMULFIX: Res = PromoteIntOp_MULFIX(N); break;
1152
1153   case ISD::FPOWI: Res = PromoteIntOp_FPOWI(N); break;
1154
1155   case ISD::VECREDUCE_ADD:
1156   case ISD::VECREDUCE_MUL:
1157   case ISD::VECREDUCE_AND:
1158   case ISD::VECREDUCE_OR:
1159   case ISD::VECREDUCE_XOR:
1160   case ISD::VECREDUCE_SMAX:
1161   case ISD::VECREDUCE_SMIN:
1162   case ISD::VECREDUCE_UMAX:
1163   case ISD::VECREDUCE_UMIN: Res = PromoteIntOp_VECREDUCE(N); break;
1164   }
1165
1166   // If the result is null, the sub-method took care of registering results etc.
1167   if (!Res.getNode()) return false;
1168
1169   // If the result is N, the sub-method updated N in place.  Tell the legalizer
1170   // core about this.
1171   if (Res.getNode() == N)
1172     return true;
1173
1174   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1175          "Invalid operand expansion");
1176
1177   ReplaceValueWith(SDValue(N, 0), Res);
1178   return false;
1179 }
1180
1181 /// PromoteSetCCOperands - Promote the operands of a comparison.  This code is
1182 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
1183 void DAGTypeLegalizer::PromoteSetCCOperands(SDValue &NewLHS,SDValue &NewRHS,
1184                                             ISD::CondCode CCCode) {
1185   // We have to insert explicit sign or zero extends. Note that we could
1186   // insert sign extends for ALL conditions. For those operations where either
1187   // zero or sign extension would be valid, use SExtOrZExtPromotedInteger
1188   // which will choose the cheapest for the target.
1189   switch (CCCode) {
1190   default: llvm_unreachable("Unknown integer comparison!");
1191   case ISD::SETEQ:
1192   case ISD::SETNE: {
1193     SDValue OpL = GetPromotedInteger(NewLHS);
1194     SDValue OpR = GetPromotedInteger(NewRHS);
1195
1196     // We would prefer to promote the comparison operand with sign extension.
1197     // If the width of OpL/OpR excluding the duplicated sign bits is no greater
1198     // than the width of NewLHS/NewRH, we can avoid inserting real truncate
1199     // instruction, which is redundant eventually.
1200     unsigned OpLEffectiveBits =
1201         OpL.getScalarValueSizeInBits() - DAG.ComputeNumSignBits(OpL) + 1;
1202     unsigned OpREffectiveBits =
1203         OpR.getScalarValueSizeInBits() - DAG.ComputeNumSignBits(OpR) + 1;
1204     if (OpLEffectiveBits <= NewLHS.getScalarValueSizeInBits() &&
1205         OpREffectiveBits <= NewRHS.getScalarValueSizeInBits()) {
1206       NewLHS = OpL;
1207       NewRHS = OpR;
1208     } else {
1209       NewLHS = SExtOrZExtPromotedInteger(NewLHS);
1210       NewRHS = SExtOrZExtPromotedInteger(NewRHS);
1211     }
1212     break;
1213   }
1214   case ISD::SETUGE:
1215   case ISD::SETUGT:
1216   case ISD::SETULE:
1217   case ISD::SETULT:
1218     NewLHS = SExtOrZExtPromotedInteger(NewLHS);
1219     NewRHS = SExtOrZExtPromotedInteger(NewRHS);
1220     break;
1221   case ISD::SETGE:
1222   case ISD::SETGT:
1223   case ISD::SETLT:
1224   case ISD::SETLE:
1225     NewLHS = SExtPromotedInteger(NewLHS);
1226     NewRHS = SExtPromotedInteger(NewRHS);
1227     break;
1228   }
1229 }
1230
1231 SDValue DAGTypeLegalizer::PromoteIntOp_ANY_EXTEND(SDNode *N) {
1232   SDValue Op = GetPromotedInteger(N->getOperand(0));
1233   return DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), N->getValueType(0), Op);
1234 }
1235
1236 SDValue DAGTypeLegalizer::PromoteIntOp_ATOMIC_STORE(AtomicSDNode *N) {
1237   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
1238   return DAG.getAtomic(N->getOpcode(), SDLoc(N), N->getMemoryVT(),
1239                        N->getChain(), N->getBasePtr(), Op2, N->getMemOperand());
1240 }
1241
1242 SDValue DAGTypeLegalizer::PromoteIntOp_BITCAST(SDNode *N) {
1243   // This should only occur in unusual situations like bitcasting to an
1244   // x86_fp80, so just turn it into a store+load
1245   return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
1246 }
1247
1248 SDValue DAGTypeLegalizer::PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo) {
1249   assert(OpNo == 2 && "Don't know how to promote this operand!");
1250
1251   SDValue LHS = N->getOperand(2);
1252   SDValue RHS = N->getOperand(3);
1253   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(1))->get());
1254
1255   // The chain (Op#0), CC (#1) and basic block destination (Op#4) are always
1256   // legal types.
1257   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1258                                 N->getOperand(1), LHS, RHS, N->getOperand(4)),
1259                  0);
1260 }
1261
1262 SDValue DAGTypeLegalizer::PromoteIntOp_BRCOND(SDNode *N, unsigned OpNo) {
1263   assert(OpNo == 1 && "only know how to promote condition");
1264
1265   // Promote all the way up to the canonical SetCC type.
1266   SDValue Cond = PromoteTargetBoolean(N->getOperand(1), MVT::Other);
1267
1268   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
1269   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), Cond,
1270                                         N->getOperand(2)), 0);
1271 }
1272
1273 SDValue DAGTypeLegalizer::PromoteIntOp_BUILD_PAIR(SDNode *N) {
1274   // Since the result type is legal, the operands must promote to it.
1275   EVT OVT = N->getOperand(0).getValueType();
1276   SDValue Lo = ZExtPromotedInteger(N->getOperand(0));
1277   SDValue Hi = GetPromotedInteger(N->getOperand(1));
1278   assert(Lo.getValueType() == N->getValueType(0) && "Operand over promoted?");
1279   SDLoc dl(N);
1280
1281   Hi = DAG.getNode(ISD::SHL, dl, N->getValueType(0), Hi,
1282                    DAG.getConstant(OVT.getSizeInBits(), dl,
1283                                    TLI.getPointerTy(DAG.getDataLayout())));
1284   return DAG.getNode(ISD::OR, dl, N->getValueType(0), Lo, Hi);
1285 }
1286
1287 SDValue DAGTypeLegalizer::PromoteIntOp_BUILD_VECTOR(SDNode *N) {
1288   // The vector type is legal but the element type is not.  This implies
1289   // that the vector is a power-of-two in length and that the element
1290   // type does not have a strange size (eg: it is not i1).
1291   EVT VecVT = N->getValueType(0);
1292   unsigned NumElts = VecVT.getVectorNumElements();
1293   assert(!((NumElts & 1) && (!TLI.isTypeLegal(VecVT))) &&
1294          "Legal vector of one illegal element?");
1295
1296   // Promote the inserted value.  The type does not need to match the
1297   // vector element type.  Check that any extra bits introduced will be
1298   // truncated away.
1299   assert(N->getOperand(0).getValueSizeInBits() >=
1300          N->getValueType(0).getScalarSizeInBits() &&
1301          "Type of inserted value narrower than vector element type!");
1302
1303   SmallVector<SDValue, 16> NewOps;
1304   for (unsigned i = 0; i < NumElts; ++i)
1305     NewOps.push_back(GetPromotedInteger(N->getOperand(i)));
1306
1307   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1308 }
1309
1310 SDValue DAGTypeLegalizer::PromoteIntOp_INSERT_VECTOR_ELT(SDNode *N,
1311                                                          unsigned OpNo) {
1312   if (OpNo == 1) {
1313     // Promote the inserted value.  This is valid because the type does not
1314     // have to match the vector element type.
1315
1316     // Check that any extra bits introduced will be truncated away.
1317     assert(N->getOperand(1).getValueSizeInBits() >=
1318            N->getValueType(0).getScalarSizeInBits() &&
1319            "Type of inserted value narrower than vector element type!");
1320     return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1321                                   GetPromotedInteger(N->getOperand(1)),
1322                                   N->getOperand(2)),
1323                    0);
1324   }
1325
1326   assert(OpNo == 2 && "Different operand and result vector types?");
1327
1328   // Promote the index.
1329   SDValue Idx = DAG.getZExtOrTrunc(N->getOperand(2), SDLoc(N),
1330                                    TLI.getVectorIdxTy(DAG.getDataLayout()));
1331   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1332                                 N->getOperand(1), Idx), 0);
1333 }
1334
1335 SDValue DAGTypeLegalizer::PromoteIntOp_SCALAR_TO_VECTOR(SDNode *N) {
1336   // Integer SCALAR_TO_VECTOR operands are implicitly truncated, so just promote
1337   // the operand in place.
1338   return SDValue(DAG.UpdateNodeOperands(N,
1339                                 GetPromotedInteger(N->getOperand(0))), 0);
1340 }
1341
1342 SDValue DAGTypeLegalizer::PromoteIntOp_SELECT(SDNode *N, unsigned OpNo) {
1343   assert(OpNo == 0 && "Only know how to promote the condition!");
1344   SDValue Cond = N->getOperand(0);
1345   EVT OpTy = N->getOperand(1).getValueType();
1346
1347   if (N->getOpcode() == ISD::VSELECT)
1348     if (SDValue Res = WidenVSELECTAndMask(N))
1349       return Res;
1350
1351   // Promote all the way up to the canonical SetCC type.
1352   EVT OpVT = N->getOpcode() == ISD::SELECT ? OpTy.getScalarType() : OpTy;
1353   Cond = PromoteTargetBoolean(Cond, OpVT);
1354
1355   return SDValue(DAG.UpdateNodeOperands(N, Cond, N->getOperand(1),
1356                                         N->getOperand(2)), 0);
1357 }
1358
1359 SDValue DAGTypeLegalizer::PromoteIntOp_SELECT_CC(SDNode *N, unsigned OpNo) {
1360   assert(OpNo == 0 && "Don't know how to promote this operand!");
1361
1362   SDValue LHS = N->getOperand(0);
1363   SDValue RHS = N->getOperand(1);
1364   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(4))->get());
1365
1366   // The CC (#4) and the possible return values (#2 and #3) have legal types.
1367   return SDValue(DAG.UpdateNodeOperands(N, LHS, RHS, N->getOperand(2),
1368                                 N->getOperand(3), N->getOperand(4)), 0);
1369 }
1370
1371 SDValue DAGTypeLegalizer::PromoteIntOp_SETCC(SDNode *N, unsigned OpNo) {
1372   assert(OpNo == 0 && "Don't know how to promote this operand!");
1373
1374   SDValue LHS = N->getOperand(0);
1375   SDValue RHS = N->getOperand(1);
1376   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(2))->get());
1377
1378   // The CC (#2) is always legal.
1379   return SDValue(DAG.UpdateNodeOperands(N, LHS, RHS, N->getOperand(2)), 0);
1380 }
1381
1382 SDValue DAGTypeLegalizer::PromoteIntOp_Shift(SDNode *N) {
1383   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1384                                 ZExtPromotedInteger(N->getOperand(1))), 0);
1385 }
1386
1387 SDValue DAGTypeLegalizer::PromoteIntOp_SIGN_EXTEND(SDNode *N) {
1388   SDValue Op = GetPromotedInteger(N->getOperand(0));
1389   SDLoc dl(N);
1390   Op = DAG.getNode(ISD::ANY_EXTEND, dl, N->getValueType(0), Op);
1391   return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Op.getValueType(),
1392                      Op, DAG.getValueType(N->getOperand(0).getValueType()));
1393 }
1394
1395 SDValue DAGTypeLegalizer::PromoteIntOp_SINT_TO_FP(SDNode *N) {
1396   return SDValue(DAG.UpdateNodeOperands(N,
1397                                 SExtPromotedInteger(N->getOperand(0))), 0);
1398 }
1399
1400 SDValue DAGTypeLegalizer::PromoteIntOp_STORE(StoreSDNode *N, unsigned OpNo){
1401   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
1402   SDValue Ch = N->getChain(), Ptr = N->getBasePtr();
1403   SDLoc dl(N);
1404
1405   SDValue Val = GetPromotedInteger(N->getValue());  // Get promoted value.
1406
1407   // Truncate the value and store the result.
1408   return DAG.getTruncStore(Ch, dl, Val, Ptr,
1409                            N->getMemoryVT(), N->getMemOperand());
1410 }
1411
1412 SDValue DAGTypeLegalizer::PromoteIntOp_MSTORE(MaskedStoreSDNode *N,
1413                                               unsigned OpNo) {
1414
1415   SDValue DataOp = N->getValue();
1416   EVT DataVT = DataOp.getValueType();
1417   SDValue Mask = N->getMask();
1418   SDLoc dl(N);
1419
1420   bool TruncateStore = false;
1421   if (OpNo == 3) {
1422     Mask = PromoteTargetBoolean(Mask, DataVT);
1423     // Update in place.
1424     SmallVector<SDValue, 4> NewOps(N->op_begin(), N->op_end());
1425     NewOps[3] = Mask;
1426     return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1427   } else { // Data operand
1428     assert(OpNo == 1 && "Unexpected operand for promotion");
1429     DataOp = GetPromotedInteger(DataOp);
1430     TruncateStore = true;
1431   }
1432
1433   return DAG.getMaskedStore(N->getChain(), dl, DataOp, N->getBasePtr(), Mask,
1434                             N->getMemoryVT(), N->getMemOperand(),
1435                             TruncateStore, N->isCompressingStore());
1436 }
1437
1438 SDValue DAGTypeLegalizer::PromoteIntOp_MLOAD(MaskedLoadSDNode *N,
1439                                              unsigned OpNo) {
1440   assert(OpNo == 2 && "Only know how to promote the mask!");
1441   EVT DataVT = N->getValueType(0);
1442   SDValue Mask = PromoteTargetBoolean(N->getOperand(OpNo), DataVT);
1443   SmallVector<SDValue, 4> NewOps(N->op_begin(), N->op_end());
1444   NewOps[OpNo] = Mask;
1445   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1446 }
1447
1448 SDValue DAGTypeLegalizer::PromoteIntOp_MGATHER(MaskedGatherSDNode *N,
1449                                                unsigned OpNo) {
1450
1451   SmallVector<SDValue, 5> NewOps(N->op_begin(), N->op_end());
1452   if (OpNo == 2) {
1453     // The Mask
1454     EVT DataVT = N->getValueType(0);
1455     NewOps[OpNo] = PromoteTargetBoolean(N->getOperand(OpNo), DataVT);
1456   } else if (OpNo == 4) {
1457     // Need to sign extend the index since the bits will likely be used.
1458     NewOps[OpNo] = SExtPromotedInteger(N->getOperand(OpNo));
1459   } else
1460     NewOps[OpNo] = GetPromotedInteger(N->getOperand(OpNo));
1461
1462   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1463 }
1464
1465 SDValue DAGTypeLegalizer::PromoteIntOp_MSCATTER(MaskedScatterSDNode *N,
1466                                                 unsigned OpNo) {
1467   SmallVector<SDValue, 5> NewOps(N->op_begin(), N->op_end());
1468   if (OpNo == 2) {
1469     // The Mask
1470     EVT DataVT = N->getValue().getValueType();
1471     NewOps[OpNo] = PromoteTargetBoolean(N->getOperand(OpNo), DataVT);
1472   } else if (OpNo == 4) {
1473     // Need to sign extend the index since the bits will likely be used.
1474     NewOps[OpNo] = SExtPromotedInteger(N->getOperand(OpNo));
1475   } else
1476     NewOps[OpNo] = GetPromotedInteger(N->getOperand(OpNo));
1477   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1478 }
1479
1480 SDValue DAGTypeLegalizer::PromoteIntOp_TRUNCATE(SDNode *N) {
1481   SDValue Op = GetPromotedInteger(N->getOperand(0));
1482   return DAG.getNode(ISD::TRUNCATE, SDLoc(N), N->getValueType(0), Op);
1483 }
1484
1485 SDValue DAGTypeLegalizer::PromoteIntOp_UINT_TO_FP(SDNode *N) {
1486   return SDValue(DAG.UpdateNodeOperands(N,
1487                                 ZExtPromotedInteger(N->getOperand(0))), 0);
1488 }
1489
1490 SDValue DAGTypeLegalizer::PromoteIntOp_ZERO_EXTEND(SDNode *N) {
1491   SDLoc dl(N);
1492   SDValue Op = GetPromotedInteger(N->getOperand(0));
1493   Op = DAG.getNode(ISD::ANY_EXTEND, dl, N->getValueType(0), Op);
1494   return DAG.getZeroExtendInReg(Op, dl,
1495                                 N->getOperand(0).getValueType().getScalarType());
1496 }
1497
1498 SDValue DAGTypeLegalizer::PromoteIntOp_ADDSUBCARRY(SDNode *N, unsigned OpNo) {
1499   assert(OpNo == 2 && "Don't know how to promote this operand!");
1500
1501   SDValue LHS = N->getOperand(0);
1502   SDValue RHS = N->getOperand(1);
1503   SDValue Carry = N->getOperand(2);
1504   SDLoc DL(N);
1505
1506   Carry = PromoteTargetBoolean(Carry, LHS.getValueType());
1507
1508   return SDValue(DAG.UpdateNodeOperands(N, LHS, RHS, Carry), 0);
1509 }
1510
1511 SDValue DAGTypeLegalizer::PromoteIntOp_MULFIX(SDNode *N) {
1512   SDValue Op2 = ZExtPromotedInteger(N->getOperand(2));
1513   return SDValue(
1514       DAG.UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1), Op2), 0);
1515 }
1516
1517 SDValue DAGTypeLegalizer::PromoteIntOp_FRAMERETURNADDR(SDNode *N) {
1518   // Promote the RETURNADDR/FRAMEADDR argument to a supported integer width.
1519   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
1520   return SDValue(DAG.UpdateNodeOperands(N, Op), 0);
1521 }
1522
1523 SDValue DAGTypeLegalizer::PromoteIntOp_PREFETCH(SDNode *N, unsigned OpNo) {
1524   assert(OpNo > 1 && "Don't know how to promote this operand!");
1525   // Promote the rw, locality, and cache type arguments to a supported integer
1526   // width.
1527   SDValue Op2 = ZExtPromotedInteger(N->getOperand(2));
1528   SDValue Op3 = ZExtPromotedInteger(N->getOperand(3));
1529   SDValue Op4 = ZExtPromotedInteger(N->getOperand(4));
1530   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),
1531                                         Op2, Op3, Op4),
1532                  0);
1533 }
1534
1535 SDValue DAGTypeLegalizer::PromoteIntOp_FPOWI(SDNode *N) {
1536   SDValue Op = SExtPromotedInteger(N->getOperand(1));
1537   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), Op), 0);
1538 }
1539
1540 SDValue DAGTypeLegalizer::PromoteIntOp_VECREDUCE(SDNode *N) {
1541   SDLoc dl(N);
1542   SDValue Op;
1543   switch (N->getOpcode()) {
1544   default: llvm_unreachable("Expected integer vector reduction");
1545   case ISD::VECREDUCE_ADD:
1546   case ISD::VECREDUCE_MUL:
1547   case ISD::VECREDUCE_AND:
1548   case ISD::VECREDUCE_OR:
1549   case ISD::VECREDUCE_XOR:
1550     Op = GetPromotedInteger(N->getOperand(0));
1551     break;
1552   case ISD::VECREDUCE_SMAX:
1553   case ISD::VECREDUCE_SMIN:
1554     Op = SExtPromotedInteger(N->getOperand(0));
1555     break;
1556   case ISD::VECREDUCE_UMAX:
1557   case ISD::VECREDUCE_UMIN:
1558     Op = ZExtPromotedInteger(N->getOperand(0));
1559     break;
1560   }
1561
1562   EVT EltVT = Op.getValueType().getVectorElementType();
1563   EVT VT = N->getValueType(0);
1564   if (VT.bitsGE(EltVT))
1565     return DAG.getNode(N->getOpcode(), SDLoc(N), VT, Op);
1566
1567   // Result size must be >= element size. If this is not the case after
1568   // promotion, also promote the result type and then truncate.
1569   SDValue Reduce = DAG.getNode(N->getOpcode(), dl, EltVT, Op);
1570   return DAG.getNode(ISD::TRUNCATE, dl, VT, Reduce);
1571 }
1572
1573 //===----------------------------------------------------------------------===//
1574 //  Integer Result Expansion
1575 //===----------------------------------------------------------------------===//
1576
1577 /// ExpandIntegerResult - This method is called when the specified result of the
1578 /// specified node is found to need expansion.  At this point, the node may also
1579 /// have invalid operands or may have other results that need promotion, we just
1580 /// know that (at least) one result needs expansion.
1581 void DAGTypeLegalizer::ExpandIntegerResult(SDNode *N, unsigned ResNo) {
1582   LLVM_DEBUG(dbgs() << "Expand integer result: "; N->dump(&DAG);
1583              dbgs() << "\n");
1584   SDValue Lo, Hi;
1585   Lo = Hi = SDValue();
1586
1587   // See if the target wants to custom expand this node.
1588   if (CustomLowerNode(N, N->getValueType(ResNo), true))
1589     return;
1590
1591   switch (N->getOpcode()) {
1592   default:
1593 #ifndef NDEBUG
1594     dbgs() << "ExpandIntegerResult #" << ResNo << ": ";
1595     N->dump(&DAG); dbgs() << "\n";
1596 #endif
1597     report_fatal_error("Do not know how to expand the result of this "
1598                        "operator!");
1599
1600   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, ResNo, Lo, Hi); break;
1601   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
1602   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
1603   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
1604
1605   case ISD::BITCAST:            ExpandRes_BITCAST(N, Lo, Hi); break;
1606   case ISD::BUILD_PAIR:         ExpandRes_BUILD_PAIR(N, Lo, Hi); break;
1607   case ISD::EXTRACT_ELEMENT:    ExpandRes_EXTRACT_ELEMENT(N, Lo, Hi); break;
1608   case ISD::EXTRACT_VECTOR_ELT: ExpandRes_EXTRACT_VECTOR_ELT(N, Lo, Hi); break;
1609   case ISD::VAARG:              ExpandRes_VAARG(N, Lo, Hi); break;
1610
1611   case ISD::ANY_EXTEND:  ExpandIntRes_ANY_EXTEND(N, Lo, Hi); break;
1612   case ISD::AssertSext:  ExpandIntRes_AssertSext(N, Lo, Hi); break;
1613   case ISD::AssertZext:  ExpandIntRes_AssertZext(N, Lo, Hi); break;
1614   case ISD::BITREVERSE:  ExpandIntRes_BITREVERSE(N, Lo, Hi); break;
1615   case ISD::BSWAP:       ExpandIntRes_BSWAP(N, Lo, Hi); break;
1616   case ISD::Constant:    ExpandIntRes_Constant(N, Lo, Hi); break;
1617   case ISD::ABS:         ExpandIntRes_ABS(N, Lo, Hi); break;
1618   case ISD::CTLZ_ZERO_UNDEF:
1619   case ISD::CTLZ:        ExpandIntRes_CTLZ(N, Lo, Hi); break;
1620   case ISD::CTPOP:       ExpandIntRes_CTPOP(N, Lo, Hi); break;
1621   case ISD::CTTZ_ZERO_UNDEF:
1622   case ISD::CTTZ:        ExpandIntRes_CTTZ(N, Lo, Hi); break;
1623   case ISD::FLT_ROUNDS_: ExpandIntRes_FLT_ROUNDS(N, Lo, Hi); break;
1624   case ISD::FP_TO_SINT:  ExpandIntRes_FP_TO_SINT(N, Lo, Hi); break;
1625   case ISD::FP_TO_UINT:  ExpandIntRes_FP_TO_UINT(N, Lo, Hi); break;
1626   case ISD::LLROUND:     ExpandIntRes_LLROUND(N, Lo, Hi); break;
1627   case ISD::LLRINT:      ExpandIntRes_LLRINT(N, Lo, Hi); break;
1628   case ISD::LOAD:        ExpandIntRes_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
1629   case ISD::MUL:         ExpandIntRes_MUL(N, Lo, Hi); break;
1630   case ISD::READCYCLECOUNTER: ExpandIntRes_READCYCLECOUNTER(N, Lo, Hi); break;
1631   case ISD::SDIV:        ExpandIntRes_SDIV(N, Lo, Hi); break;
1632   case ISD::SIGN_EXTEND: ExpandIntRes_SIGN_EXTEND(N, Lo, Hi); break;
1633   case ISD::SIGN_EXTEND_INREG: ExpandIntRes_SIGN_EXTEND_INREG(N, Lo, Hi); break;
1634   case ISD::SREM:        ExpandIntRes_SREM(N, Lo, Hi); break;
1635   case ISD::TRUNCATE:    ExpandIntRes_TRUNCATE(N, Lo, Hi); break;
1636   case ISD::UDIV:        ExpandIntRes_UDIV(N, Lo, Hi); break;
1637   case ISD::UREM:        ExpandIntRes_UREM(N, Lo, Hi); break;
1638   case ISD::ZERO_EXTEND: ExpandIntRes_ZERO_EXTEND(N, Lo, Hi); break;
1639   case ISD::ATOMIC_LOAD: ExpandIntRes_ATOMIC_LOAD(N, Lo, Hi); break;
1640
1641   case ISD::ATOMIC_LOAD_ADD:
1642   case ISD::ATOMIC_LOAD_SUB:
1643   case ISD::ATOMIC_LOAD_AND:
1644   case ISD::ATOMIC_LOAD_CLR:
1645   case ISD::ATOMIC_LOAD_OR:
1646   case ISD::ATOMIC_LOAD_XOR:
1647   case ISD::ATOMIC_LOAD_NAND:
1648   case ISD::ATOMIC_LOAD_MIN:
1649   case ISD::ATOMIC_LOAD_MAX:
1650   case ISD::ATOMIC_LOAD_UMIN:
1651   case ISD::ATOMIC_LOAD_UMAX:
1652   case ISD::ATOMIC_SWAP:
1653   case ISD::ATOMIC_CMP_SWAP: {
1654     std::pair<SDValue, SDValue> Tmp = ExpandAtomic(N);
1655     SplitInteger(Tmp.first, Lo, Hi);
1656     ReplaceValueWith(SDValue(N, 1), Tmp.second);
1657     break;
1658   }
1659   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS: {
1660     AtomicSDNode *AN = cast<AtomicSDNode>(N);
1661     SDVTList VTs = DAG.getVTList(N->getValueType(0), MVT::Other);
1662     SDValue Tmp = DAG.getAtomicCmpSwap(
1663         ISD::ATOMIC_CMP_SWAP, SDLoc(N), AN->getMemoryVT(), VTs,
1664         N->getOperand(0), N->getOperand(1), N->getOperand(2), N->getOperand(3),
1665         AN->getMemOperand());
1666
1667     // Expanding to the strong ATOMIC_CMP_SWAP node means we can determine
1668     // success simply by comparing the loaded value against the ingoing
1669     // comparison.
1670     SDValue Success = DAG.getSetCC(SDLoc(N), N->getValueType(1), Tmp,
1671                                    N->getOperand(2), ISD::SETEQ);
1672
1673     SplitInteger(Tmp, Lo, Hi);
1674     ReplaceValueWith(SDValue(N, 1), Success);
1675     ReplaceValueWith(SDValue(N, 2), Tmp.getValue(1));
1676     break;
1677   }
1678
1679   case ISD::AND:
1680   case ISD::OR:
1681   case ISD::XOR: ExpandIntRes_Logical(N, Lo, Hi); break;
1682
1683   case ISD::UMAX:
1684   case ISD::SMAX:
1685   case ISD::UMIN:
1686   case ISD::SMIN: ExpandIntRes_MINMAX(N, Lo, Hi); break;
1687
1688   case ISD::ADD:
1689   case ISD::SUB: ExpandIntRes_ADDSUB(N, Lo, Hi); break;
1690
1691   case ISD::ADDC:
1692   case ISD::SUBC: ExpandIntRes_ADDSUBC(N, Lo, Hi); break;
1693
1694   case ISD::ADDE:
1695   case ISD::SUBE: ExpandIntRes_ADDSUBE(N, Lo, Hi); break;
1696
1697   case ISD::ADDCARRY:
1698   case ISD::SUBCARRY: ExpandIntRes_ADDSUBCARRY(N, Lo, Hi); break;
1699
1700   case ISD::SHL:
1701   case ISD::SRA:
1702   case ISD::SRL: ExpandIntRes_Shift(N, Lo, Hi); break;
1703
1704   case ISD::SADDO:
1705   case ISD::SSUBO: ExpandIntRes_SADDSUBO(N, Lo, Hi); break;
1706   case ISD::UADDO:
1707   case ISD::USUBO: ExpandIntRes_UADDSUBO(N, Lo, Hi); break;
1708   case ISD::UMULO:
1709   case ISD::SMULO: ExpandIntRes_XMULO(N, Lo, Hi); break;
1710
1711   case ISD::SADDSAT:
1712   case ISD::UADDSAT:
1713   case ISD::SSUBSAT:
1714   case ISD::USUBSAT: ExpandIntRes_ADDSUBSAT(N, Lo, Hi); break;
1715
1716   case ISD::SMULFIX:
1717   case ISD::SMULFIXSAT:
1718   case ISD::UMULFIX: ExpandIntRes_MULFIX(N, Lo, Hi); break;
1719
1720   case ISD::VECREDUCE_ADD:
1721   case ISD::VECREDUCE_MUL:
1722   case ISD::VECREDUCE_AND:
1723   case ISD::VECREDUCE_OR:
1724   case ISD::VECREDUCE_XOR:
1725   case ISD::VECREDUCE_SMAX:
1726   case ISD::VECREDUCE_SMIN:
1727   case ISD::VECREDUCE_UMAX:
1728   case ISD::VECREDUCE_UMIN: ExpandIntRes_VECREDUCE(N, Lo, Hi); break;
1729   }
1730
1731   // If Lo/Hi is null, the sub-method took care of registering results etc.
1732   if (Lo.getNode())
1733     SetExpandedInteger(SDValue(N, ResNo), Lo, Hi);
1734 }
1735
1736 /// Lower an atomic node to the appropriate builtin call.
1737 std::pair <SDValue, SDValue> DAGTypeLegalizer::ExpandAtomic(SDNode *Node) {
1738   unsigned Opc = Node->getOpcode();
1739   MVT VT = cast<AtomicSDNode>(Node)->getMemoryVT().getSimpleVT();
1740   RTLIB::Libcall LC = RTLIB::getSYNC(Opc, VT);
1741   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected atomic op or value type!");
1742
1743   return ExpandChainLibCall(LC, Node, false);
1744 }
1745
1746 /// N is a shift by a value that needs to be expanded,
1747 /// and the shift amount is a constant 'Amt'.  Expand the operation.
1748 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, const APInt &Amt,
1749                                              SDValue &Lo, SDValue &Hi) {
1750   SDLoc DL(N);
1751   // Expand the incoming operand to be shifted, so that we have its parts
1752   SDValue InL, InH;
1753   GetExpandedInteger(N->getOperand(0), InL, InH);
1754
1755   // Though Amt shouldn't usually be 0, it's possible. E.g. when legalization
1756   // splitted a vector shift, like this: <op1, op2> SHL <0, 2>.
1757   if (!Amt) {
1758     Lo = InL;
1759     Hi = InH;
1760     return;
1761   }
1762
1763   EVT NVT = InL.getValueType();
1764   unsigned VTBits = N->getValueType(0).getSizeInBits();
1765   unsigned NVTBits = NVT.getSizeInBits();
1766   EVT ShTy = N->getOperand(1).getValueType();
1767
1768   if (N->getOpcode() == ISD::SHL) {
1769     if (Amt.ugt(VTBits)) {
1770       Lo = Hi = DAG.getConstant(0, DL, NVT);
1771     } else if (Amt.ugt(NVTBits)) {
1772       Lo = DAG.getConstant(0, DL, NVT);
1773       Hi = DAG.getNode(ISD::SHL, DL,
1774                        NVT, InL, DAG.getConstant(Amt - NVTBits, DL, ShTy));
1775     } else if (Amt == NVTBits) {
1776       Lo = DAG.getConstant(0, DL, NVT);
1777       Hi = InL;
1778     } else {
1779       Lo = DAG.getNode(ISD::SHL, DL, NVT, InL, DAG.getConstant(Amt, DL, ShTy));
1780       Hi = DAG.getNode(ISD::OR, DL, NVT,
1781                        DAG.getNode(ISD::SHL, DL, NVT, InH,
1782                                    DAG.getConstant(Amt, DL, ShTy)),
1783                        DAG.getNode(ISD::SRL, DL, NVT, InL,
1784                                    DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
1785     }
1786     return;
1787   }
1788
1789   if (N->getOpcode() == ISD::SRL) {
1790     if (Amt.ugt(VTBits)) {
1791       Lo = Hi = DAG.getConstant(0, DL, NVT);
1792     } else if (Amt.ugt(NVTBits)) {
1793       Lo = DAG.getNode(ISD::SRL, DL,
1794                        NVT, InH, DAG.getConstant(Amt - NVTBits, DL, ShTy));
1795       Hi = DAG.getConstant(0, DL, NVT);
1796     } else if (Amt == NVTBits) {
1797       Lo = InH;
1798       Hi = DAG.getConstant(0, DL, NVT);
1799     } else {
1800       Lo = DAG.getNode(ISD::OR, DL, NVT,
1801                        DAG.getNode(ISD::SRL, DL, NVT, InL,
1802                                    DAG.getConstant(Amt, DL, ShTy)),
1803                        DAG.getNode(ISD::SHL, DL, NVT, InH,
1804                                    DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
1805       Hi = DAG.getNode(ISD::SRL, DL, NVT, InH, DAG.getConstant(Amt, DL, ShTy));
1806     }
1807     return;
1808   }
1809
1810   assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
1811   if (Amt.ugt(VTBits)) {
1812     Hi = Lo = DAG.getNode(ISD::SRA, DL, NVT, InH,
1813                           DAG.getConstant(NVTBits - 1, DL, ShTy));
1814   } else if (Amt.ugt(NVTBits)) {
1815     Lo = DAG.getNode(ISD::SRA, DL, NVT, InH,
1816                      DAG.getConstant(Amt - NVTBits, DL, ShTy));
1817     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH,
1818                      DAG.getConstant(NVTBits - 1, DL, ShTy));
1819   } else if (Amt == NVTBits) {
1820     Lo = InH;
1821     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH,
1822                      DAG.getConstant(NVTBits - 1, DL, ShTy));
1823   } else {
1824     Lo = DAG.getNode(ISD::OR, DL, NVT,
1825                      DAG.getNode(ISD::SRL, DL, NVT, InL,
1826                                  DAG.getConstant(Amt, DL, ShTy)),
1827                      DAG.getNode(ISD::SHL, DL, NVT, InH,
1828                                  DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
1829     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH, DAG.getConstant(Amt, DL, ShTy));
1830   }
1831 }
1832
1833 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
1834 /// this shift based on knowledge of the high bit of the shift amount.  If we
1835 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
1836 /// shift amount.
1837 bool DAGTypeLegalizer::
1838 ExpandShiftWithKnownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
1839   SDValue Amt = N->getOperand(1);
1840   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1841   EVT ShTy = Amt.getValueType();
1842   unsigned ShBits = ShTy.getScalarSizeInBits();
1843   unsigned NVTBits = NVT.getScalarSizeInBits();
1844   assert(isPowerOf2_32(NVTBits) &&
1845          "Expanded integer type size not a power of two!");
1846   SDLoc dl(N);
1847
1848   APInt HighBitMask = APInt::getHighBitsSet(ShBits, ShBits - Log2_32(NVTBits));
1849   KnownBits Known = DAG.computeKnownBits(N->getOperand(1));
1850
1851   // If we don't know anything about the high bits, exit.
1852   if (((Known.Zero|Known.One) & HighBitMask) == 0)
1853     return false;
1854
1855   // Get the incoming operand to be shifted.
1856   SDValue InL, InH;
1857   GetExpandedInteger(N->getOperand(0), InL, InH);
1858
1859   // If we know that any of the high bits of the shift amount are one, then we
1860   // can do this as a couple of simple shifts.
1861   if (Known.One.intersects(HighBitMask)) {
1862     // Mask out the high bit, which we know is set.
1863     Amt = DAG.getNode(ISD::AND, dl, ShTy, Amt,
1864                       DAG.getConstant(~HighBitMask, dl, ShTy));
1865
1866     switch (N->getOpcode()) {
1867     default: llvm_unreachable("Unknown shift");
1868     case ISD::SHL:
1869       Lo = DAG.getConstant(0, dl, NVT);              // Low part is zero.
1870       Hi = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt); // High part from Lo part.
1871       return true;
1872     case ISD::SRL:
1873       Hi = DAG.getConstant(0, dl, NVT);              // Hi part is zero.
1874       Lo = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt); // Lo part from Hi part.
1875       return true;
1876     case ISD::SRA:
1877       Hi = DAG.getNode(ISD::SRA, dl, NVT, InH,       // Sign extend high part.
1878                        DAG.getConstant(NVTBits - 1, dl, ShTy));
1879       Lo = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt); // Lo part from Hi part.
1880       return true;
1881     }
1882   }
1883
1884   // If we know that all of the high bits of the shift amount are zero, then we
1885   // can do this as a couple of simple shifts.
1886   if (HighBitMask.isSubsetOf(Known.Zero)) {
1887     // Calculate 31-x. 31 is used instead of 32 to avoid creating an undefined
1888     // shift if x is zero.  We can use XOR here because x is known to be smaller
1889     // than 32.
1890     SDValue Amt2 = DAG.getNode(ISD::XOR, dl, ShTy, Amt,
1891                                DAG.getConstant(NVTBits - 1, dl, ShTy));
1892
1893     unsigned Op1, Op2;
1894     switch (N->getOpcode()) {
1895     default: llvm_unreachable("Unknown shift");
1896     case ISD::SHL:  Op1 = ISD::SHL; Op2 = ISD::SRL; break;
1897     case ISD::SRL:
1898     case ISD::SRA:  Op1 = ISD::SRL; Op2 = ISD::SHL; break;
1899     }
1900
1901     // When shifting right the arithmetic for Lo and Hi is swapped.
1902     if (N->getOpcode() != ISD::SHL)
1903       std::swap(InL, InH);
1904
1905     // Use a little trick to get the bits that move from Lo to Hi. First
1906     // shift by one bit.
1907     SDValue Sh1 = DAG.getNode(Op2, dl, NVT, InL, DAG.getConstant(1, dl, ShTy));
1908     // Then compute the remaining shift with amount-1.
1909     SDValue Sh2 = DAG.getNode(Op2, dl, NVT, Sh1, Amt2);
1910
1911     Lo = DAG.getNode(N->getOpcode(), dl, NVT, InL, Amt);
1912     Hi = DAG.getNode(ISD::OR, dl, NVT, DAG.getNode(Op1, dl, NVT, InH, Amt),Sh2);
1913
1914     if (N->getOpcode() != ISD::SHL)
1915       std::swap(Hi, Lo);
1916     return true;
1917   }
1918
1919   return false;
1920 }
1921
1922 /// ExpandShiftWithUnknownAmountBit - Fully general expansion of integer shift
1923 /// of any size.
1924 bool DAGTypeLegalizer::
1925 ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
1926   SDValue Amt = N->getOperand(1);
1927   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1928   EVT ShTy = Amt.getValueType();
1929   unsigned NVTBits = NVT.getSizeInBits();
1930   assert(isPowerOf2_32(NVTBits) &&
1931          "Expanded integer type size not a power of two!");
1932   SDLoc dl(N);
1933
1934   // Get the incoming operand to be shifted.
1935   SDValue InL, InH;
1936   GetExpandedInteger(N->getOperand(0), InL, InH);
1937
1938   SDValue NVBitsNode = DAG.getConstant(NVTBits, dl, ShTy);
1939   SDValue AmtExcess = DAG.getNode(ISD::SUB, dl, ShTy, Amt, NVBitsNode);
1940   SDValue AmtLack = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
1941   SDValue isShort = DAG.getSetCC(dl, getSetCCResultType(ShTy),
1942                                  Amt, NVBitsNode, ISD::SETULT);
1943   SDValue isZero = DAG.getSetCC(dl, getSetCCResultType(ShTy),
1944                                 Amt, DAG.getConstant(0, dl, ShTy),
1945                                 ISD::SETEQ);
1946
1947   SDValue LoS, HiS, LoL, HiL;
1948   switch (N->getOpcode()) {
1949   default: llvm_unreachable("Unknown shift");
1950   case ISD::SHL:
1951     // Short: ShAmt < NVTBits
1952     LoS = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt);
1953     HiS = DAG.getNode(ISD::OR, dl, NVT,
1954                       DAG.getNode(ISD::SHL, dl, NVT, InH, Amt),
1955                       DAG.getNode(ISD::SRL, dl, NVT, InL, AmtLack));
1956
1957     // Long: ShAmt >= NVTBits
1958     LoL = DAG.getConstant(0, dl, NVT);                    // Lo part is zero.
1959     HiL = DAG.getNode(ISD::SHL, dl, NVT, InL, AmtExcess); // Hi from Lo part.
1960
1961     Lo = DAG.getSelect(dl, NVT, isShort, LoS, LoL);
1962     Hi = DAG.getSelect(dl, NVT, isZero, InH,
1963                        DAG.getSelect(dl, NVT, isShort, HiS, HiL));
1964     return true;
1965   case ISD::SRL:
1966     // Short: ShAmt < NVTBits
1967     HiS = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt);
1968     LoS = DAG.getNode(ISD::OR, dl, NVT,
1969                       DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
1970     // FIXME: If Amt is zero, the following shift generates an undefined result
1971     // on some architectures.
1972                       DAG.getNode(ISD::SHL, dl, NVT, InH, AmtLack));
1973
1974     // Long: ShAmt >= NVTBits
1975     HiL = DAG.getConstant(0, dl, NVT);                    // Hi part is zero.
1976     LoL = DAG.getNode(ISD::SRL, dl, NVT, InH, AmtExcess); // Lo from Hi part.
1977
1978     Lo = DAG.getSelect(dl, NVT, isZero, InL,
1979                        DAG.getSelect(dl, NVT, isShort, LoS, LoL));
1980     Hi = DAG.getSelect(dl, NVT, isShort, HiS, HiL);
1981     return true;
1982   case ISD::SRA:
1983     // Short: ShAmt < NVTBits
1984     HiS = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt);
1985     LoS = DAG.getNode(ISD::OR, dl, NVT,
1986                       DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
1987                       DAG.getNode(ISD::SHL, dl, NVT, InH, AmtLack));
1988
1989     // Long: ShAmt >= NVTBits
1990     HiL = DAG.getNode(ISD::SRA, dl, NVT, InH,             // Sign of Hi part.
1991                       DAG.getConstant(NVTBits - 1, dl, ShTy));
1992     LoL = DAG.getNode(ISD::SRA, dl, NVT, InH, AmtExcess); // Lo from Hi part.
1993
1994     Lo = DAG.getSelect(dl, NVT, isZero, InL,
1995                        DAG.getSelect(dl, NVT, isShort, LoS, LoL));
1996     Hi = DAG.getSelect(dl, NVT, isShort, HiS, HiL);
1997     return true;
1998   }
1999 }
2000
2001 static std::pair<ISD::CondCode, ISD::NodeType> getExpandedMinMaxOps(int Op) {
2002
2003   switch (Op) {
2004     default: llvm_unreachable("invalid min/max opcode");
2005     case ISD::SMAX:
2006       return std::make_pair(ISD::SETGT, ISD::UMAX);
2007     case ISD::UMAX:
2008       return std::make_pair(ISD::SETUGT, ISD::UMAX);
2009     case ISD::SMIN:
2010       return std::make_pair(ISD::SETLT, ISD::UMIN);
2011     case ISD::UMIN:
2012       return std::make_pair(ISD::SETULT, ISD::UMIN);
2013   }
2014 }
2015
2016 void DAGTypeLegalizer::ExpandIntRes_MINMAX(SDNode *N,
2017                                            SDValue &Lo, SDValue &Hi) {
2018   SDLoc DL(N);
2019   ISD::NodeType LoOpc;
2020   ISD::CondCode CondC;
2021   std::tie(CondC, LoOpc) = getExpandedMinMaxOps(N->getOpcode());
2022
2023   // Expand the subcomponents.
2024   SDValue LHSL, LHSH, RHSL, RHSH;
2025   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2026   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
2027
2028   // Value types
2029   EVT NVT = LHSL.getValueType();
2030   EVT CCT = getSetCCResultType(NVT);
2031
2032   // Hi part is always the same op
2033   Hi = DAG.getNode(N->getOpcode(), DL, NVT, {LHSH, RHSH});
2034
2035   // We need to know whether to select Lo part that corresponds to 'winning'
2036   // Hi part or if Hi parts are equal.
2037   SDValue IsHiLeft = DAG.getSetCC(DL, CCT, LHSH, RHSH, CondC);
2038   SDValue IsHiEq = DAG.getSetCC(DL, CCT, LHSH, RHSH, ISD::SETEQ);
2039
2040   // Lo part corresponding to the 'winning' Hi part
2041   SDValue LoCmp = DAG.getSelect(DL, NVT, IsHiLeft, LHSL, RHSL);
2042
2043   // Recursed Lo part if Hi parts are equal, this uses unsigned version
2044   SDValue LoMinMax = DAG.getNode(LoOpc, DL, NVT, {LHSL, RHSL});
2045
2046   Lo = DAG.getSelect(DL, NVT, IsHiEq, LoMinMax, LoCmp);
2047 }
2048
2049 void DAGTypeLegalizer::ExpandIntRes_ADDSUB(SDNode *N,
2050                                            SDValue &Lo, SDValue &Hi) {
2051   SDLoc dl(N);
2052   // Expand the subcomponents.
2053   SDValue LHSL, LHSH, RHSL, RHSH;
2054   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2055   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
2056
2057   EVT NVT = LHSL.getValueType();
2058   SDValue LoOps[2] = { LHSL, RHSL };
2059   SDValue HiOps[3] = { LHSH, RHSH };
2060
2061   bool HasOpCarry = TLI.isOperationLegalOrCustom(
2062       N->getOpcode() == ISD::ADD ? ISD::ADDCARRY : ISD::SUBCARRY,
2063       TLI.getTypeToExpandTo(*DAG.getContext(), NVT));
2064   if (HasOpCarry) {
2065     SDVTList VTList = DAG.getVTList(NVT, getSetCCResultType(NVT));
2066     if (N->getOpcode() == ISD::ADD) {
2067       Lo = DAG.getNode(ISD::UADDO, dl, VTList, LoOps);
2068       HiOps[2] = Lo.getValue(1);
2069       Hi = DAG.getNode(ISD::ADDCARRY, dl, VTList, HiOps);
2070     } else {
2071       Lo = DAG.getNode(ISD::USUBO, dl, VTList, LoOps);
2072       HiOps[2] = Lo.getValue(1);
2073       Hi = DAG.getNode(ISD::SUBCARRY, dl, VTList, HiOps);
2074     }
2075     return;
2076   }
2077
2078   // Do not generate ADDC/ADDE or SUBC/SUBE if the target does not support
2079   // them.  TODO: Teach operation legalization how to expand unsupported
2080   // ADDC/ADDE/SUBC/SUBE.  The problem is that these operations generate
2081   // a carry of type MVT::Glue, but there doesn't seem to be any way to
2082   // generate a value of this type in the expanded code sequence.
2083   bool hasCarry =
2084     TLI.isOperationLegalOrCustom(N->getOpcode() == ISD::ADD ?
2085                                    ISD::ADDC : ISD::SUBC,
2086                                  TLI.getTypeToExpandTo(*DAG.getContext(), NVT));
2087
2088   if (hasCarry) {
2089     SDVTList VTList = DAG.getVTList(NVT, MVT::Glue);
2090     if (N->getOpcode() == ISD::ADD) {
2091       Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps);
2092       HiOps[2] = Lo.getValue(1);
2093       Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps);
2094     } else {
2095       Lo = DAG.getNode(ISD::SUBC, dl, VTList, LoOps);
2096       HiOps[2] = Lo.getValue(1);
2097       Hi = DAG.getNode(ISD::SUBE, dl, VTList, HiOps);
2098     }
2099     return;
2100   }
2101
2102   bool hasOVF =
2103     TLI.isOperationLegalOrCustom(N->getOpcode() == ISD::ADD ?
2104                                    ISD::UADDO : ISD::USUBO,
2105                                  TLI.getTypeToExpandTo(*DAG.getContext(), NVT));
2106   TargetLoweringBase::BooleanContent BoolType = TLI.getBooleanContents(NVT);
2107
2108   if (hasOVF) {
2109     EVT OvfVT = getSetCCResultType(NVT);
2110     SDVTList VTList = DAG.getVTList(NVT, OvfVT);
2111     int RevOpc;
2112     if (N->getOpcode() == ISD::ADD) {
2113       RevOpc = ISD::SUB;
2114       Lo = DAG.getNode(ISD::UADDO, dl, VTList, LoOps);
2115       Hi = DAG.getNode(ISD::ADD, dl, NVT, makeArrayRef(HiOps, 2));
2116     } else {
2117       RevOpc = ISD::ADD;
2118       Lo = DAG.getNode(ISD::USUBO, dl, VTList, LoOps);
2119       Hi = DAG.getNode(ISD::SUB, dl, NVT, makeArrayRef(HiOps, 2));
2120     }
2121     SDValue OVF = Lo.getValue(1);
2122
2123     switch (BoolType) {
2124     case TargetLoweringBase::UndefinedBooleanContent:
2125       OVF = DAG.getNode(ISD::AND, dl, OvfVT, DAG.getConstant(1, dl, OvfVT), OVF);
2126       LLVM_FALLTHROUGH;
2127     case TargetLoweringBase::ZeroOrOneBooleanContent:
2128       OVF = DAG.getZExtOrTrunc(OVF, dl, NVT);
2129       Hi = DAG.getNode(N->getOpcode(), dl, NVT, Hi, OVF);
2130       break;
2131     case TargetLoweringBase::ZeroOrNegativeOneBooleanContent:
2132       OVF = DAG.getSExtOrTrunc(OVF, dl, NVT);
2133       Hi = DAG.getNode(RevOpc, dl, NVT, Hi, OVF);
2134     }
2135     return;
2136   }
2137
2138   if (N->getOpcode() == ISD::ADD) {
2139     Lo = DAG.getNode(ISD::ADD, dl, NVT, LoOps);
2140     Hi = DAG.getNode(ISD::ADD, dl, NVT, makeArrayRef(HiOps, 2));
2141     SDValue Cmp1 = DAG.getSetCC(dl, getSetCCResultType(NVT), Lo, LoOps[0],
2142                                 ISD::SETULT);
2143
2144     if (BoolType == TargetLoweringBase::ZeroOrOneBooleanContent) {
2145       SDValue Carry = DAG.getZExtOrTrunc(Cmp1, dl, NVT);
2146       Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, Carry);
2147       return;
2148     }
2149
2150     SDValue Carry1 = DAG.getSelect(dl, NVT, Cmp1,
2151                                    DAG.getConstant(1, dl, NVT),
2152                                    DAG.getConstant(0, dl, NVT));
2153     SDValue Cmp2 = DAG.getSetCC(dl, getSetCCResultType(NVT), Lo, LoOps[1],
2154                                 ISD::SETULT);
2155     SDValue Carry2 = DAG.getSelect(dl, NVT, Cmp2,
2156                                    DAG.getConstant(1, dl, NVT), Carry1);
2157     Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, Carry2);
2158   } else {
2159     Lo = DAG.getNode(ISD::SUB, dl, NVT, LoOps);
2160     Hi = DAG.getNode(ISD::SUB, dl, NVT, makeArrayRef(HiOps, 2));
2161     SDValue Cmp =
2162       DAG.getSetCC(dl, getSetCCResultType(LoOps[0].getValueType()),
2163                    LoOps[0], LoOps[1], ISD::SETULT);
2164
2165     SDValue Borrow;
2166     if (BoolType == TargetLoweringBase::ZeroOrOneBooleanContent)
2167       Borrow = DAG.getZExtOrTrunc(Cmp, dl, NVT);
2168     else
2169       Borrow = DAG.getSelect(dl, NVT, Cmp, DAG.getConstant(1, dl, NVT),
2170                              DAG.getConstant(0, dl, NVT));
2171
2172     Hi = DAG.getNode(ISD::SUB, dl, NVT, Hi, Borrow);
2173   }
2174 }
2175
2176 void DAGTypeLegalizer::ExpandIntRes_ADDSUBC(SDNode *N,
2177                                             SDValue &Lo, SDValue &Hi) {
2178   // Expand the subcomponents.
2179   SDValue LHSL, LHSH, RHSL, RHSH;
2180   SDLoc dl(N);
2181   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2182   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
2183   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Glue);
2184   SDValue LoOps[2] = { LHSL, RHSL };
2185   SDValue HiOps[3] = { LHSH, RHSH };
2186
2187   if (N->getOpcode() == ISD::ADDC) {
2188     Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps);
2189     HiOps[2] = Lo.getValue(1);
2190     Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps);
2191   } else {
2192     Lo = DAG.getNode(ISD::SUBC, dl, VTList, LoOps);
2193     HiOps[2] = Lo.getValue(1);
2194     Hi = DAG.getNode(ISD::SUBE, dl, VTList, HiOps);
2195   }
2196
2197   // Legalized the flag result - switch anything that used the old flag to
2198   // use the new one.
2199   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
2200 }
2201
2202 void DAGTypeLegalizer::ExpandIntRes_ADDSUBE(SDNode *N,
2203                                             SDValue &Lo, SDValue &Hi) {
2204   // Expand the subcomponents.
2205   SDValue LHSL, LHSH, RHSL, RHSH;
2206   SDLoc dl(N);
2207   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2208   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
2209   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Glue);
2210   SDValue LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
2211   SDValue HiOps[3] = { LHSH, RHSH };
2212
2213   Lo = DAG.getNode(N->getOpcode(), dl, VTList, LoOps);
2214   HiOps[2] = Lo.getValue(1);
2215   Hi = DAG.getNode(N->getOpcode(), dl, VTList, HiOps);
2216
2217   // Legalized the flag result - switch anything that used the old flag to
2218   // use the new one.
2219   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
2220 }
2221
2222 void DAGTypeLegalizer::ExpandIntRes_UADDSUBO(SDNode *N,
2223                                              SDValue &Lo, SDValue &Hi) {
2224   SDValue LHS = N->getOperand(0);
2225   SDValue RHS = N->getOperand(1);
2226   SDLoc dl(N);
2227
2228   SDValue Ovf;
2229
2230   bool HasOpCarry = TLI.isOperationLegalOrCustom(
2231       N->getOpcode() == ISD::ADD ? ISD::ADDCARRY : ISD::SUBCARRY,
2232       TLI.getTypeToExpandTo(*DAG.getContext(), LHS.getValueType()));
2233
2234   if (HasOpCarry) {
2235     // Expand the subcomponents.
2236     SDValue LHSL, LHSH, RHSL, RHSH;
2237     GetExpandedInteger(LHS, LHSL, LHSH);
2238     GetExpandedInteger(RHS, RHSL, RHSH);
2239     SDVTList VTList = DAG.getVTList(LHSL.getValueType(), N->getValueType(1));
2240     SDValue LoOps[2] = { LHSL, RHSL };
2241     SDValue HiOps[3] = { LHSH, RHSH };
2242
2243     unsigned Opc = N->getOpcode() == ISD::UADDO ? ISD::ADDCARRY : ISD::SUBCARRY;
2244     Lo = DAG.getNode(N->getOpcode(), dl, VTList, LoOps);
2245     HiOps[2] = Lo.getValue(1);
2246     Hi = DAG.getNode(Opc, dl, VTList, HiOps);
2247
2248     Ovf = Hi.getValue(1);
2249   } else {
2250     // Expand the result by simply replacing it with the equivalent
2251     // non-overflow-checking operation.
2252     auto Opc = N->getOpcode() == ISD::UADDO ? ISD::ADD : ISD::SUB;
2253     SDValue Sum = DAG.getNode(Opc, dl, LHS.getValueType(), LHS, RHS);
2254     SplitInteger(Sum, Lo, Hi);
2255
2256     // Calculate the overflow: addition overflows iff a + b < a, and subtraction
2257     // overflows iff a - b > a.
2258     auto Cond = N->getOpcode() == ISD::UADDO ? ISD::SETULT : ISD::SETUGT;
2259     Ovf = DAG.getSetCC(dl, N->getValueType(1), Sum, LHS, Cond);
2260   }
2261
2262   // Legalized the flag result - switch anything that used the old flag to
2263   // use the new one.
2264   ReplaceValueWith(SDValue(N, 1), Ovf);
2265 }
2266
2267 void DAGTypeLegalizer::ExpandIntRes_ADDSUBCARRY(SDNode *N,
2268                                                 SDValue &Lo, SDValue &Hi) {
2269   // Expand the subcomponents.
2270   SDValue LHSL, LHSH, RHSL, RHSH;
2271   SDLoc dl(N);
2272   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2273   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
2274   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), N->getValueType(1));
2275   SDValue LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
2276   SDValue HiOps[3] = { LHSH, RHSH, SDValue() };
2277
2278   Lo = DAG.getNode(N->getOpcode(), dl, VTList, LoOps);
2279   HiOps[2] = Lo.getValue(1);
2280   Hi = DAG.getNode(N->getOpcode(), dl, VTList, HiOps);
2281
2282   // Legalized the flag result - switch anything that used the old flag to
2283   // use the new one.
2284   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
2285 }
2286
2287 void DAGTypeLegalizer::ExpandIntRes_ANY_EXTEND(SDNode *N,
2288                                                SDValue &Lo, SDValue &Hi) {
2289   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2290   SDLoc dl(N);
2291   SDValue Op = N->getOperand(0);
2292   if (Op.getValueType().bitsLE(NVT)) {
2293     // The low part is any extension of the input (which degenerates to a copy).
2294     Lo = DAG.getNode(ISD::ANY_EXTEND, dl, NVT, Op);
2295     Hi = DAG.getUNDEF(NVT);   // The high part is undefined.
2296   } else {
2297     // For example, extension of an i48 to an i64.  The operand type necessarily
2298     // promotes to the result type, so will end up being expanded too.
2299     assert(getTypeAction(Op.getValueType()) ==
2300            TargetLowering::TypePromoteInteger &&
2301            "Only know how to promote this result!");
2302     SDValue Res = GetPromotedInteger(Op);
2303     assert(Res.getValueType() == N->getValueType(0) &&
2304            "Operand over promoted?");
2305     // Split the promoted operand.  This will simplify when it is expanded.
2306     SplitInteger(Res, Lo, Hi);
2307   }
2308 }
2309
2310 void DAGTypeLegalizer::ExpandIntRes_AssertSext(SDNode *N,
2311                                                SDValue &Lo, SDValue &Hi) {
2312   SDLoc dl(N);
2313   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2314   EVT NVT = Lo.getValueType();
2315   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
2316   unsigned NVTBits = NVT.getSizeInBits();
2317   unsigned EVTBits = EVT.getSizeInBits();
2318
2319   if (NVTBits < EVTBits) {
2320     Hi = DAG.getNode(ISD::AssertSext, dl, NVT, Hi,
2321                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
2322                                                         EVTBits - NVTBits)));
2323   } else {
2324     Lo = DAG.getNode(ISD::AssertSext, dl, NVT, Lo, DAG.getValueType(EVT));
2325     // The high part replicates the sign bit of Lo, make it explicit.
2326     Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
2327                      DAG.getConstant(NVTBits - 1, dl,
2328                                      TLI.getPointerTy(DAG.getDataLayout())));
2329   }
2330 }
2331
2332 void DAGTypeLegalizer::ExpandIntRes_AssertZext(SDNode *N,
2333                                                SDValue &Lo, SDValue &Hi) {
2334   SDLoc dl(N);
2335   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2336   EVT NVT = Lo.getValueType();
2337   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
2338   unsigned NVTBits = NVT.getSizeInBits();
2339   unsigned EVTBits = EVT.getSizeInBits();
2340
2341   if (NVTBits < EVTBits) {
2342     Hi = DAG.getNode(ISD::AssertZext, dl, NVT, Hi,
2343                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
2344                                                         EVTBits - NVTBits)));
2345   } else {
2346     Lo = DAG.getNode(ISD::AssertZext, dl, NVT, Lo, DAG.getValueType(EVT));
2347     // The high part must be zero, make it explicit.
2348     Hi = DAG.getConstant(0, dl, NVT);
2349   }
2350 }
2351
2352 void DAGTypeLegalizer::ExpandIntRes_BITREVERSE(SDNode *N,
2353                                                SDValue &Lo, SDValue &Hi) {
2354   SDLoc dl(N);
2355   GetExpandedInteger(N->getOperand(0), Hi, Lo);  // Note swapped operands.
2356   Lo = DAG.getNode(ISD::BITREVERSE, dl, Lo.getValueType(), Lo);
2357   Hi = DAG.getNode(ISD::BITREVERSE, dl, Hi.getValueType(), Hi);
2358 }
2359
2360 void DAGTypeLegalizer::ExpandIntRes_BSWAP(SDNode *N,
2361                                           SDValue &Lo, SDValue &Hi) {
2362   SDLoc dl(N);
2363   GetExpandedInteger(N->getOperand(0), Hi, Lo);  // Note swapped operands.
2364   Lo = DAG.getNode(ISD::BSWAP, dl, Lo.getValueType(), Lo);
2365   Hi = DAG.getNode(ISD::BSWAP, dl, Hi.getValueType(), Hi);
2366 }
2367
2368 void DAGTypeLegalizer::ExpandIntRes_Constant(SDNode *N,
2369                                              SDValue &Lo, SDValue &Hi) {
2370   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2371   unsigned NBitWidth = NVT.getSizeInBits();
2372   auto Constant = cast<ConstantSDNode>(N);
2373   const APInt &Cst = Constant->getAPIntValue();
2374   bool IsTarget = Constant->isTargetOpcode();
2375   bool IsOpaque = Constant->isOpaque();
2376   SDLoc dl(N);
2377   Lo = DAG.getConstant(Cst.trunc(NBitWidth), dl, NVT, IsTarget, IsOpaque);
2378   Hi = DAG.getConstant(Cst.lshr(NBitWidth).trunc(NBitWidth), dl, NVT, IsTarget,
2379                        IsOpaque);
2380 }
2381
2382 void DAGTypeLegalizer::ExpandIntRes_ABS(SDNode *N, SDValue &Lo, SDValue &Hi) {
2383   SDLoc dl(N);
2384
2385   // abs(HiLo) -> (Hi < 0 ? -HiLo : HiLo)
2386   EVT VT = N->getValueType(0);
2387   SDValue N0 = N->getOperand(0);
2388   SDValue Neg = DAG.getNode(ISD::SUB, dl, VT,
2389                             DAG.getConstant(0, dl, VT), N0);
2390   SDValue NegLo, NegHi;
2391   SplitInteger(Neg, NegLo, NegHi);
2392
2393   GetExpandedInteger(N0, Lo, Hi);
2394   EVT NVT = Lo.getValueType();
2395   SDValue HiIsNeg = DAG.getSetCC(dl, getSetCCResultType(NVT),
2396                                  DAG.getConstant(0, dl, NVT), Hi, ISD::SETGT);
2397   Lo = DAG.getSelect(dl, NVT, HiIsNeg, NegLo, Lo);
2398   Hi = DAG.getSelect(dl, NVT, HiIsNeg, NegHi, Hi);
2399 }
2400
2401 void DAGTypeLegalizer::ExpandIntRes_CTLZ(SDNode *N,
2402                                          SDValue &Lo, SDValue &Hi) {
2403   SDLoc dl(N);
2404   // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
2405   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2406   EVT NVT = Lo.getValueType();
2407
2408   SDValue HiNotZero = DAG.getSetCC(dl, getSetCCResultType(NVT), Hi,
2409                                    DAG.getConstant(0, dl, NVT), ISD::SETNE);
2410
2411   SDValue LoLZ = DAG.getNode(N->getOpcode(), dl, NVT, Lo);
2412   SDValue HiLZ = DAG.getNode(ISD::CTLZ_ZERO_UNDEF, dl, NVT, Hi);
2413
2414   Lo = DAG.getSelect(dl, NVT, HiNotZero, HiLZ,
2415                      DAG.getNode(ISD::ADD, dl, NVT, LoLZ,
2416                                  DAG.getConstant(NVT.getSizeInBits(), dl,
2417                                                  NVT)));
2418   Hi = DAG.getConstant(0, dl, NVT);
2419 }
2420
2421 void DAGTypeLegalizer::ExpandIntRes_CTPOP(SDNode *N,
2422                                           SDValue &Lo, SDValue &Hi) {
2423   SDLoc dl(N);
2424   // ctpop(HiLo) -> ctpop(Hi)+ctpop(Lo)
2425   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2426   EVT NVT = Lo.getValueType();
2427   Lo = DAG.getNode(ISD::ADD, dl, NVT, DAG.getNode(ISD::CTPOP, dl, NVT, Lo),
2428                    DAG.getNode(ISD::CTPOP, dl, NVT, Hi));
2429   Hi = DAG.getConstant(0, dl, NVT);
2430 }
2431
2432 void DAGTypeLegalizer::ExpandIntRes_CTTZ(SDNode *N,
2433                                          SDValue &Lo, SDValue &Hi) {
2434   SDLoc dl(N);
2435   // cttz (HiLo) -> Lo != 0 ? cttz(Lo) : (cttz(Hi)+32)
2436   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2437   EVT NVT = Lo.getValueType();
2438
2439   SDValue LoNotZero = DAG.getSetCC(dl, getSetCCResultType(NVT), Lo,
2440                                    DAG.getConstant(0, dl, NVT), ISD::SETNE);
2441
2442   SDValue LoLZ = DAG.getNode(ISD::CTTZ_ZERO_UNDEF, dl, NVT, Lo);
2443   SDValue HiLZ = DAG.getNode(N->getOpcode(), dl, NVT, Hi);
2444
2445   Lo = DAG.getSelect(dl, NVT, LoNotZero, LoLZ,
2446                      DAG.getNode(ISD::ADD, dl, NVT, HiLZ,
2447                                  DAG.getConstant(NVT.getSizeInBits(), dl,
2448                                                  NVT)));
2449   Hi = DAG.getConstant(0, dl, NVT);
2450 }
2451
2452 void DAGTypeLegalizer::ExpandIntRes_FLT_ROUNDS(SDNode *N, SDValue &Lo,
2453                                                SDValue &Hi) {
2454   SDLoc dl(N);
2455   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2456   unsigned NBitWidth = NVT.getSizeInBits();
2457
2458   EVT ShiftAmtTy = TLI.getShiftAmountTy(NVT, DAG.getDataLayout());
2459   Lo = DAG.getNode(ISD::FLT_ROUNDS_, dl, NVT);
2460   // The high part is the sign of Lo, as -1 is a valid value for FLT_ROUNDS
2461   Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
2462                    DAG.getConstant(NBitWidth - 1, dl, ShiftAmtTy));
2463 }
2464
2465 void DAGTypeLegalizer::ExpandIntRes_FP_TO_SINT(SDNode *N, SDValue &Lo,
2466                                                SDValue &Hi) {
2467   SDLoc dl(N);
2468   EVT VT = N->getValueType(0);
2469
2470   SDValue Op = N->getOperand(0);
2471   if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteFloat)
2472     Op = GetPromotedFloat(Op);
2473
2474   RTLIB::Libcall LC = RTLIB::getFPTOSINT(Op.getValueType(), VT);
2475   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected fp-to-sint conversion!");
2476   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Op, true/*irrelevant*/, dl).first,
2477                Lo, Hi);
2478 }
2479
2480 void DAGTypeLegalizer::ExpandIntRes_FP_TO_UINT(SDNode *N, SDValue &Lo,
2481                                                SDValue &Hi) {
2482   SDLoc dl(N);
2483   EVT VT = N->getValueType(0);
2484
2485   SDValue Op = N->getOperand(0);
2486   if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteFloat)
2487     Op = GetPromotedFloat(Op);
2488
2489   RTLIB::Libcall LC = RTLIB::getFPTOUINT(Op.getValueType(), VT);
2490   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected fp-to-uint conversion!");
2491   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Op, false/*irrelevant*/, dl).first,
2492                Lo, Hi);
2493 }
2494
2495 void DAGTypeLegalizer::ExpandIntRes_LLROUND(SDNode *N, SDValue &Lo,
2496                                             SDValue &Hi) {
2497   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2498   EVT VT = N->getOperand(0).getValueType().getSimpleVT().SimpleTy;
2499   if (VT == MVT::f32)
2500     LC = RTLIB::LLROUND_F32;
2501   else if (VT == MVT::f64)
2502     LC = RTLIB::LLROUND_F64;
2503   else if (VT == MVT::f80)
2504     LC = RTLIB::LLROUND_F80;
2505   else if (VT == MVT::f128)
2506     LC = RTLIB::LLROUND_F128;
2507   else if (VT == MVT::ppcf128)
2508     LC = RTLIB::LLROUND_PPCF128;
2509   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected llround input type!");
2510
2511   SDValue Op = N->getOperand(0);
2512   if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteFloat)
2513     Op = GetPromotedFloat(Op);
2514
2515   SDLoc dl(N);
2516   EVT RetVT = N->getValueType(0);
2517   SplitInteger(TLI.makeLibCall(DAG, LC, RetVT, Op, true/*irrelevant*/, dl).first,
2518                Lo, Hi);
2519 }
2520
2521 void DAGTypeLegalizer::ExpandIntRes_LLRINT(SDNode *N, SDValue &Lo,
2522                                             SDValue &Hi) {
2523   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2524   EVT VT = N->getOperand(0).getValueType().getSimpleVT().SimpleTy;
2525   if (VT == MVT::f32)
2526     LC = RTLIB::LLRINT_F32;
2527   else if (VT == MVT::f64)
2528     LC = RTLIB::LLRINT_F64;
2529   else if (VT == MVT::f80)
2530     LC = RTLIB::LLRINT_F80;
2531   else if (VT == MVT::f128)
2532     LC = RTLIB::LLRINT_F128;
2533   else if (VT == MVT::ppcf128)
2534     LC = RTLIB::LLRINT_PPCF128;
2535   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected llrint input type!");
2536
2537   SDValue Op = N->getOperand(0);
2538   if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteFloat)
2539     Op = GetPromotedFloat(Op);
2540
2541   SDLoc dl(N);
2542   EVT RetVT = N->getValueType(0);
2543   SplitInteger(TLI.makeLibCall(DAG, LC, RetVT, Op, true/*irrelevant*/, dl).first,
2544                Lo, Hi);
2545 }
2546
2547 void DAGTypeLegalizer::ExpandIntRes_LOAD(LoadSDNode *N,
2548                                          SDValue &Lo, SDValue &Hi) {
2549   if (ISD::isNormalLoad(N)) {
2550     ExpandRes_NormalLoad(N, Lo, Hi);
2551     return;
2552   }
2553
2554   assert(ISD::isUNINDEXEDLoad(N) && "Indexed load during type legalization!");
2555
2556   EVT VT = N->getValueType(0);
2557   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2558   SDValue Ch  = N->getChain();
2559   SDValue Ptr = N->getBasePtr();
2560   ISD::LoadExtType ExtType = N->getExtensionType();
2561   unsigned Alignment = N->getAlignment();
2562   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
2563   AAMDNodes AAInfo = N->getAAInfo();
2564   SDLoc dl(N);
2565
2566   assert(NVT.isByteSized() && "Expanded type not byte sized!");
2567
2568   if (N->getMemoryVT().bitsLE(NVT)) {
2569     EVT MemVT = N->getMemoryVT();
2570
2571     Lo = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getPointerInfo(), MemVT,
2572                         Alignment, MMOFlags, AAInfo);
2573
2574     // Remember the chain.
2575     Ch = Lo.getValue(1);
2576
2577     if (ExtType == ISD::SEXTLOAD) {
2578       // The high part is obtained by SRA'ing all but one of the bits of the
2579       // lo part.
2580       unsigned LoSize = Lo.getValueSizeInBits();
2581       Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
2582                        DAG.getConstant(LoSize - 1, dl,
2583                                        TLI.getPointerTy(DAG.getDataLayout())));
2584     } else if (ExtType == ISD::ZEXTLOAD) {
2585       // The high part is just a zero.
2586       Hi = DAG.getConstant(0, dl, NVT);
2587     } else {
2588       assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
2589       // The high part is undefined.
2590       Hi = DAG.getUNDEF(NVT);
2591     }
2592   } else if (DAG.getDataLayout().isLittleEndian()) {
2593     // Little-endian - low bits are at low addresses.
2594     Lo = DAG.getLoad(NVT, dl, Ch, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
2595                      AAInfo);
2596
2597     unsigned ExcessBits =
2598       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
2599     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
2600
2601     // Increment the pointer to the other half.
2602     unsigned IncrementSize = NVT.getSizeInBits()/8;
2603     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
2604                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
2605     Hi = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr,
2606                         N->getPointerInfo().getWithOffset(IncrementSize), NEVT,
2607                         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
2608
2609     // Build a factor node to remember that this load is independent of the
2610     // other one.
2611     Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
2612                      Hi.getValue(1));
2613   } else {
2614     // Big-endian - high bits are at low addresses.  Favor aligned loads at
2615     // the cost of some bit-fiddling.
2616     EVT MemVT = N->getMemoryVT();
2617     unsigned EBytes = MemVT.getStoreSize();
2618     unsigned IncrementSize = NVT.getSizeInBits()/8;
2619     unsigned ExcessBits = (EBytes - IncrementSize)*8;
2620
2621     // Load both the high bits and maybe some of the low bits.
2622     Hi = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getPointerInfo(),
2623                         EVT::getIntegerVT(*DAG.getContext(),
2624                                           MemVT.getSizeInBits() - ExcessBits),
2625                         Alignment, MMOFlags, AAInfo);
2626
2627     // Increment the pointer to the other half.
2628     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
2629                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
2630     // Load the rest of the low bits.
2631     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, NVT, Ch, Ptr,
2632                         N->getPointerInfo().getWithOffset(IncrementSize),
2633                         EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
2634                         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
2635
2636     // Build a factor node to remember that this load is independent of the
2637     // other one.
2638     Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
2639                      Hi.getValue(1));
2640
2641     if (ExcessBits < NVT.getSizeInBits()) {
2642       // Transfer low bits from the bottom of Hi to the top of Lo.
2643       Lo = DAG.getNode(
2644           ISD::OR, dl, NVT, Lo,
2645           DAG.getNode(ISD::SHL, dl, NVT, Hi,
2646                       DAG.getConstant(ExcessBits, dl,
2647                                       TLI.getPointerTy(DAG.getDataLayout()))));
2648       // Move high bits to the right position in Hi.
2649       Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, dl, NVT,
2650                        Hi,
2651                        DAG.getConstant(NVT.getSizeInBits() - ExcessBits, dl,
2652                                        TLI.getPointerTy(DAG.getDataLayout())));
2653     }
2654   }
2655
2656   // Legalize the chain result - switch anything that used the old chain to
2657   // use the new one.
2658   ReplaceValueWith(SDValue(N, 1), Ch);
2659 }
2660
2661 void DAGTypeLegalizer::ExpandIntRes_Logical(SDNode *N,
2662                                             SDValue &Lo, SDValue &Hi) {
2663   SDLoc dl(N);
2664   SDValue LL, LH, RL, RH;
2665   GetExpandedInteger(N->getOperand(0), LL, LH);
2666   GetExpandedInteger(N->getOperand(1), RL, RH);
2667   Lo = DAG.getNode(N->getOpcode(), dl, LL.getValueType(), LL, RL);
2668   Hi = DAG.getNode(N->getOpcode(), dl, LL.getValueType(), LH, RH);
2669 }
2670
2671 void DAGTypeLegalizer::ExpandIntRes_MUL(SDNode *N,
2672                                         SDValue &Lo, SDValue &Hi) {
2673   EVT VT = N->getValueType(0);
2674   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2675   SDLoc dl(N);
2676
2677   SDValue LL, LH, RL, RH;
2678   GetExpandedInteger(N->getOperand(0), LL, LH);
2679   GetExpandedInteger(N->getOperand(1), RL, RH);
2680
2681   if (TLI.expandMUL(N, Lo, Hi, NVT, DAG,
2682                     TargetLowering::MulExpansionKind::OnlyLegalOrCustom,
2683                     LL, LH, RL, RH))
2684     return;
2685
2686   // If nothing else, we can make a libcall.
2687   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2688   if (VT == MVT::i16)
2689     LC = RTLIB::MUL_I16;
2690   else if (VT == MVT::i32)
2691     LC = RTLIB::MUL_I32;
2692   else if (VT == MVT::i64)
2693     LC = RTLIB::MUL_I64;
2694   else if (VT == MVT::i128)
2695     LC = RTLIB::MUL_I128;
2696
2697   if (LC == RTLIB::UNKNOWN_LIBCALL || !TLI.getLibcallName(LC)) {
2698     // We'll expand the multiplication by brute force because we have no other
2699     // options. This is a trivially-generalized version of the code from
2700     // Hacker's Delight (itself derived from Knuth's Algorithm M from section
2701     // 4.3.1).
2702     unsigned Bits = NVT.getSizeInBits();
2703     unsigned HalfBits = Bits >> 1;
2704     SDValue Mask = DAG.getConstant(APInt::getLowBitsSet(Bits, HalfBits), dl,
2705                                    NVT);
2706     SDValue LLL = DAG.getNode(ISD::AND, dl, NVT, LL, Mask);
2707     SDValue RLL = DAG.getNode(ISD::AND, dl, NVT, RL, Mask);
2708
2709     SDValue T = DAG.getNode(ISD::MUL, dl, NVT, LLL, RLL);
2710     SDValue TL = DAG.getNode(ISD::AND, dl, NVT, T, Mask);
2711
2712     EVT ShiftAmtTy = TLI.getShiftAmountTy(NVT, DAG.getDataLayout());
2713     if (APInt::getMaxValue(ShiftAmtTy.getSizeInBits()).ult(HalfBits)) {
2714       // The type from TLI is too small to fit the shift amount we want.
2715       // Override it with i32. The shift will have to be legalized.
2716       ShiftAmtTy = MVT::i32;
2717     }
2718     SDValue Shift = DAG.getConstant(HalfBits, dl, ShiftAmtTy);
2719     SDValue TH = DAG.getNode(ISD::SRL, dl, NVT, T, Shift);
2720     SDValue LLH = DAG.getNode(ISD::SRL, dl, NVT, LL, Shift);
2721     SDValue RLH = DAG.getNode(ISD::SRL, dl, NVT, RL, Shift);
2722
2723     SDValue U = DAG.getNode(ISD::ADD, dl, NVT,
2724                             DAG.getNode(ISD::MUL, dl, NVT, LLH, RLL), TH);
2725     SDValue UL = DAG.getNode(ISD::AND, dl, NVT, U, Mask);
2726     SDValue UH = DAG.getNode(ISD::SRL, dl, NVT, U, Shift);
2727
2728     SDValue V = DAG.getNode(ISD::ADD, dl, NVT,
2729                             DAG.getNode(ISD::MUL, dl, NVT, LLL, RLH), UL);
2730     SDValue VH = DAG.getNode(ISD::SRL, dl, NVT, V, Shift);
2731
2732     SDValue W = DAG.getNode(ISD::ADD, dl, NVT,
2733                             DAG.getNode(ISD::MUL, dl, NVT, LLH, RLH),
2734                             DAG.getNode(ISD::ADD, dl, NVT, UH, VH));
2735     Lo = DAG.getNode(ISD::ADD, dl, NVT, TL,
2736                      DAG.getNode(ISD::SHL, dl, NVT, V, Shift));
2737
2738     Hi = DAG.getNode(ISD::ADD, dl, NVT, W,
2739                      DAG.getNode(ISD::ADD, dl, NVT,
2740                                  DAG.getNode(ISD::MUL, dl, NVT, RH, LL),
2741                                  DAG.getNode(ISD::MUL, dl, NVT, RL, LH)));
2742     return;
2743   }
2744
2745   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2746   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true/*irrelevant*/, dl).first,
2747                Lo, Hi);
2748 }
2749
2750 void DAGTypeLegalizer::ExpandIntRes_READCYCLECOUNTER(SDNode *N, SDValue &Lo,
2751                                                      SDValue &Hi) {
2752   SDLoc DL(N);
2753   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2754   SDVTList VTs = DAG.getVTList(NVT, NVT, MVT::Other);
2755   SDValue R = DAG.getNode(N->getOpcode(), DL, VTs, N->getOperand(0));
2756   Lo = R.getValue(0);
2757   Hi = R.getValue(1);
2758   ReplaceValueWith(SDValue(N, 1), R.getValue(2));
2759 }
2760
2761 void DAGTypeLegalizer::ExpandIntRes_ADDSUBSAT(SDNode *N, SDValue &Lo,
2762                                               SDValue &Hi) {
2763   SDValue Result = TLI.expandAddSubSat(N, DAG);
2764   SplitInteger(Result, Lo, Hi);
2765 }
2766
2767 /// This performs an expansion of the integer result for a fixed point
2768 /// multiplication. The default expansion performs rounding down towards
2769 /// negative infinity, though targets that do care about rounding should specify
2770 /// a target hook for rounding and provide their own expansion or lowering of
2771 /// fixed point multiplication to be consistent with rounding.
2772 void DAGTypeLegalizer::ExpandIntRes_MULFIX(SDNode *N, SDValue &Lo,
2773                                            SDValue &Hi) {
2774   SDLoc dl(N);
2775   EVT VT = N->getValueType(0);
2776   unsigned VTSize = VT.getScalarSizeInBits();
2777   SDValue LHS = N->getOperand(0);
2778   SDValue RHS = N->getOperand(1);
2779   uint64_t Scale = N->getConstantOperandVal(2);
2780   bool Saturating = N->getOpcode() == ISD::SMULFIXSAT;
2781   EVT BoolVT = getSetCCResultType(VT);
2782   SDValue Zero = DAG.getConstant(0, dl, VT);
2783   if (!Scale) {
2784     SDValue Result;
2785     if (!Saturating) {
2786       Result = DAG.getNode(ISD::MUL, dl, VT, LHS, RHS);
2787     } else {
2788       Result = DAG.getNode(ISD::SMULO, dl, DAG.getVTList(VT, BoolVT), LHS, RHS);
2789       SDValue Product = Result.getValue(0);
2790       SDValue Overflow = Result.getValue(1);
2791
2792       APInt MinVal = APInt::getSignedMinValue(VTSize);
2793       APInt MaxVal = APInt::getSignedMaxValue(VTSize);
2794       SDValue SatMin = DAG.getConstant(MinVal, dl, VT);
2795       SDValue SatMax = DAG.getConstant(MaxVal, dl, VT);
2796       SDValue ProdNeg = DAG.getSetCC(dl, BoolVT, Product, Zero, ISD::SETLT);
2797       Result = DAG.getSelect(dl, VT, ProdNeg, SatMax, SatMin);
2798       Result = DAG.getSelect(dl, VT, Overflow, Result, Product);
2799     }
2800     SplitInteger(Result, Lo, Hi);
2801     return;
2802   }
2803
2804   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2805   SDValue LL, LH, RL, RH;
2806   GetExpandedInteger(LHS, LL, LH);
2807   GetExpandedInteger(RHS, RL, RH);
2808   SmallVector<SDValue, 4> Result;
2809
2810   bool Signed = (N->getOpcode() == ISD::SMULFIX ||
2811                  N->getOpcode() == ISD::SMULFIXSAT);
2812   unsigned LoHiOp = Signed ? ISD::SMUL_LOHI : ISD::UMUL_LOHI;
2813   if (!TLI.expandMUL_LOHI(LoHiOp, VT, dl, LHS, RHS, Result, NVT, DAG,
2814                           TargetLowering::MulExpansionKind::OnlyLegalOrCustom,
2815                           LL, LH, RL, RH)) {
2816     report_fatal_error("Unable to expand MUL_FIX using MUL_LOHI.");
2817     return;
2818   }
2819
2820   unsigned NVTSize = NVT.getScalarSizeInBits();
2821   assert((VTSize == NVTSize * 2) && "Expected the new value type to be half "
2822                                     "the size of the current value type");
2823   EVT ShiftTy = TLI.getShiftAmountTy(NVT, DAG.getDataLayout());
2824
2825   // Shift whole amount by scale.
2826   SDValue ResultLL = Result[0];
2827   SDValue ResultLH = Result[1];
2828   SDValue ResultHL = Result[2];
2829   SDValue ResultHH = Result[3];
2830
2831   SDValue SatMax, SatMin;
2832   SDValue NVTZero = DAG.getConstant(0, dl, NVT);
2833   SDValue NVTNeg1 = DAG.getConstant(-1, dl, NVT);
2834   EVT BoolNVT = getSetCCResultType(NVT);
2835
2836   // After getting the multplication result in 4 parts, we need to perform a
2837   // shift right by the amount of the scale to get the result in that scale.
2838   // Let's say we multiply 2 64 bit numbers. The resulting value can be held in
2839   // 128 bits that are cut into 4 32-bit parts:
2840   //
2841   //      HH       HL       LH       LL
2842   //  |---32---|---32---|---32---|---32---|
2843   // 128      96       64       32        0
2844   //
2845   //                    |------VTSize-----|
2846   //
2847   //                             |NVTSize-|
2848   //
2849   // The resulting Lo and Hi will only need to be one of these 32-bit parts
2850   // after shifting.
2851   if (Scale < NVTSize) {
2852     // If the scale is less than the size of the VT we expand to, the Hi and
2853     // Lo of the result will be in the first 2 parts of the result after
2854     // shifting right. This only requires shifting by the scale as far as the
2855     // third part in the result (ResultHL).
2856     SDValue SRLAmnt = DAG.getConstant(Scale, dl, ShiftTy);
2857     SDValue SHLAmnt = DAG.getConstant(NVTSize - Scale, dl, ShiftTy);
2858     Lo = DAG.getNode(ISD::SRL, dl, NVT, ResultLL, SRLAmnt);
2859     Lo = DAG.getNode(ISD::OR, dl, NVT, Lo,
2860                      DAG.getNode(ISD::SHL, dl, NVT, ResultLH, SHLAmnt));
2861     Hi = DAG.getNode(ISD::SRL, dl, NVT, ResultLH, SRLAmnt);
2862     Hi = DAG.getNode(ISD::OR, dl, NVT, Hi,
2863                      DAG.getNode(ISD::SHL, dl, NVT, ResultHL, SHLAmnt));
2864
2865     // We cannot overflow past HH when multiplying 2 ints of size VTSize, so the
2866     // highest bit of HH determines saturation direction in the event of
2867     // saturation.
2868     // The number of overflow bits we can check are VTSize - Scale + 1 (we
2869     // include the sign bit). If these top bits are > 0, then we overflowed past
2870     // the max value. If these top bits are < -1, then we overflowed past the
2871     // min value. Otherwise, we did not overflow.
2872     if (Saturating) {
2873       unsigned OverflowBits = VTSize - Scale + 1;
2874       assert(OverflowBits <= VTSize && OverflowBits > NVTSize &&
2875              "Extent of overflow bits must start within HL");
2876       SDValue HLHiMask = DAG.getConstant(
2877           APInt::getHighBitsSet(NVTSize, OverflowBits - NVTSize), dl, NVT);
2878       SDValue HLLoMask = DAG.getConstant(
2879           APInt::getLowBitsSet(NVTSize, VTSize - OverflowBits), dl, NVT);
2880
2881       // HH > 0 or HH == 0 && HL > HLLoMask
2882       SDValue HHPos = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTZero, ISD::SETGT);
2883       SDValue HHZero = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTZero, ISD::SETEQ);
2884       SDValue HLPos =
2885           DAG.getSetCC(dl, BoolNVT, ResultHL, HLLoMask, ISD::SETUGT);
2886       SatMax = DAG.getNode(ISD::OR, dl, BoolNVT, HHPos,
2887                            DAG.getNode(ISD::AND, dl, BoolNVT, HHZero, HLPos));
2888
2889       // HH < -1 or HH == -1 && HL < HLHiMask
2890       SDValue HHNeg = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTNeg1, ISD::SETLT);
2891       SDValue HHNeg1 = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTNeg1, ISD::SETEQ);
2892       SDValue HLNeg =
2893           DAG.getSetCC(dl, BoolNVT, ResultHL, HLHiMask, ISD::SETULT);
2894       SatMin = DAG.getNode(ISD::OR, dl, BoolNVT, HHNeg,
2895                            DAG.getNode(ISD::AND, dl, BoolNVT, HHNeg1, HLNeg));
2896     }
2897   } else if (Scale == NVTSize) {
2898     // If the scales are equal, Lo and Hi are ResultLH and Result HL,
2899     // respectively. Avoid shifting to prevent undefined behavior.
2900     Lo = ResultLH;
2901     Hi = ResultHL;
2902
2903     // We overflow max if HH > 0 or HH == 0 && HL sign bit is 1.
2904     // We overflow min if HH < -1 or HH == -1 && HL sign bit is 0.
2905     if (Saturating) {
2906       SDValue HHPos = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTZero, ISD::SETGT);
2907       SDValue HHZero = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTZero, ISD::SETEQ);
2908       SDValue HLNeg = DAG.getSetCC(dl, BoolNVT, ResultHL, NVTZero, ISD::SETLT);
2909       SatMax = DAG.getNode(ISD::OR, dl, BoolNVT, HHPos,
2910                            DAG.getNode(ISD::AND, dl, BoolNVT, HHZero, HLNeg));
2911
2912       SDValue HHNeg = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTNeg1, ISD::SETLT);
2913       SDValue HHNeg1 = DAG.getSetCC(dl, BoolNVT, ResultHH, NVTNeg1, ISD::SETEQ);
2914       SDValue HLPos = DAG.getSetCC(dl, BoolNVT, ResultHL, NVTZero, ISD::SETGE);
2915       SatMin = DAG.getNode(ISD::OR, dl, BoolNVT, HHNeg,
2916                            DAG.getNode(ISD::AND, dl, BoolNVT, HHNeg1, HLPos));
2917     }
2918   } else if (Scale < VTSize) {
2919     // If the scale is instead less than the old VT size, but greater than or
2920     // equal to the expanded VT size, the first part of the result (ResultLL) is
2921     // no longer a part of Lo because it would be scaled out anyway. Instead we
2922     // can start shifting right from the fourth part (ResultHH) to the second
2923     // part (ResultLH), and Result LH will be the new Lo.
2924     SDValue SRLAmnt = DAG.getConstant(Scale - NVTSize, dl, ShiftTy);
2925     SDValue SHLAmnt = DAG.getConstant(VTSize - Scale, dl, ShiftTy);
2926     Lo = DAG.getNode(ISD::SRL, dl, NVT, ResultLH, SRLAmnt);
2927     Lo = DAG.getNode(ISD::OR, dl, NVT, Lo,
2928                      DAG.getNode(ISD::SHL, dl, NVT, ResultHL, SHLAmnt));
2929     Hi = DAG.getNode(ISD::SRL, dl, NVT, ResultHL, SRLAmnt);
2930     Hi = DAG.getNode(ISD::OR, dl, NVT, Hi,
2931                      DAG.getNode(ISD::SHL, dl, NVT, ResultHH, SHLAmnt));
2932
2933     // This is similar to the case when we saturate if Scale < NVTSize, but we
2934     // only need to chech HH.
2935     if (Saturating) {
2936       unsigned OverflowBits = VTSize - Scale + 1;
2937       SDValue HHHiMask = DAG.getConstant(
2938           APInt::getHighBitsSet(NVTSize, OverflowBits), dl, NVT);
2939       SDValue HHLoMask = DAG.getConstant(
2940           APInt::getLowBitsSet(NVTSize, NVTSize - OverflowBits), dl, NVT);
2941
2942       SatMax = DAG.getSetCC(dl, BoolNVT, ResultHH, HHLoMask, ISD::SETGT);
2943       SatMin = DAG.getSetCC(dl, BoolNVT, ResultHH, HHHiMask, ISD::SETLT);
2944     }
2945   } else if (Scale == VTSize) {
2946     assert(
2947         !Signed &&
2948         "Only unsigned types can have a scale equal to the operand bit width");
2949
2950     Lo = ResultHL;
2951     Hi = ResultHH;
2952   } else {
2953     llvm_unreachable("Expected the scale to be less than or equal to the width "
2954                      "of the operands");
2955   }
2956
2957   if (Saturating) {
2958     APInt LHMax = APInt::getSignedMaxValue(NVTSize);
2959     APInt LLMax = APInt::getAllOnesValue(NVTSize);
2960     APInt LHMin = APInt::getSignedMinValue(NVTSize);
2961     Hi = DAG.getSelect(dl, NVT, SatMax, DAG.getConstant(LHMax, dl, NVT), Hi);
2962     Hi = DAG.getSelect(dl, NVT, SatMin, DAG.getConstant(LHMin, dl, NVT), Hi);
2963     Lo = DAG.getSelect(dl, NVT, SatMax, DAG.getConstant(LLMax, dl, NVT), Lo);
2964     Lo = DAG.getSelect(dl, NVT, SatMin, NVTZero, Lo);
2965   }
2966 }
2967
2968 void DAGTypeLegalizer::ExpandIntRes_SADDSUBO(SDNode *Node,
2969                                              SDValue &Lo, SDValue &Hi) {
2970   SDValue LHS = Node->getOperand(0);
2971   SDValue RHS = Node->getOperand(1);
2972   SDLoc dl(Node);
2973
2974   // Expand the result by simply replacing it with the equivalent
2975   // non-overflow-checking operation.
2976   SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
2977                             ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
2978                             LHS, RHS);
2979   SplitInteger(Sum, Lo, Hi);
2980
2981   // Compute the overflow.
2982   //
2983   //   LHSSign -> LHS >= 0
2984   //   RHSSign -> RHS >= 0
2985   //   SumSign -> Sum >= 0
2986   //
2987   //   Add:
2988   //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
2989   //   Sub:
2990   //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
2991   //
2992   EVT OType = Node->getValueType(1);
2993   SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
2994
2995   SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE);
2996   SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE);
2997   SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign,
2998                                     Node->getOpcode() == ISD::SADDO ?
2999                                     ISD::SETEQ : ISD::SETNE);
3000
3001   SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE);
3002   SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE);
3003
3004   SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE);
3005
3006   // Use the calculated overflow everywhere.
3007   ReplaceValueWith(SDValue(Node, 1), Cmp);
3008 }
3009
3010 void DAGTypeLegalizer::ExpandIntRes_SDIV(SDNode *N,
3011                                          SDValue &Lo, SDValue &Hi) {
3012   EVT VT = N->getValueType(0);
3013   SDLoc dl(N);
3014   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
3015
3016   if (TLI.getOperationAction(ISD::SDIVREM, VT) == TargetLowering::Custom) {
3017     SDValue Res = DAG.getNode(ISD::SDIVREM, dl, DAG.getVTList(VT, VT), Ops);
3018     SplitInteger(Res.getValue(0), Lo, Hi);
3019     return;
3020   }
3021
3022   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3023   if (VT == MVT::i16)
3024     LC = RTLIB::SDIV_I16;
3025   else if (VT == MVT::i32)
3026     LC = RTLIB::SDIV_I32;
3027   else if (VT == MVT::i64)
3028     LC = RTLIB::SDIV_I64;
3029   else if (VT == MVT::i128)
3030     LC = RTLIB::SDIV_I128;
3031   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SDIV!");
3032
3033   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true, dl).first, Lo, Hi);
3034 }
3035
3036 void DAGTypeLegalizer::ExpandIntRes_Shift(SDNode *N,
3037                                           SDValue &Lo, SDValue &Hi) {
3038   EVT VT = N->getValueType(0);
3039   SDLoc dl(N);
3040
3041   // If we can emit an efficient shift operation, do so now.  Check to see if
3042   // the RHS is a constant.
3043   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
3044     return ExpandShiftByConstant(N, CN->getAPIntValue(), Lo, Hi);
3045
3046   // If we can determine that the high bit of the shift is zero or one, even if
3047   // the low bits are variable, emit this shift in an optimized form.
3048   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
3049     return;
3050
3051   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
3052   unsigned PartsOpc;
3053   if (N->getOpcode() == ISD::SHL) {
3054     PartsOpc = ISD::SHL_PARTS;
3055   } else if (N->getOpcode() == ISD::SRL) {
3056     PartsOpc = ISD::SRL_PARTS;
3057   } else {
3058     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
3059     PartsOpc = ISD::SRA_PARTS;
3060   }
3061
3062   // Next check to see if the target supports this SHL_PARTS operation or if it
3063   // will custom expand it. Don't lower this to SHL_PARTS when we optimise for
3064   // size, but create a libcall instead.
3065   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3066   TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
3067   const bool LegalOrCustom =
3068     (Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
3069     Action == TargetLowering::Custom;
3070
3071   if (LegalOrCustom && TLI.shouldExpandShift(DAG, N)) {
3072     // Expand the subcomponents.
3073     SDValue LHSL, LHSH;
3074     GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
3075     EVT VT = LHSL.getValueType();
3076
3077     // If the shift amount operand is coming from a vector legalization it may
3078     // have an illegal type.  Fix that first by casting the operand, otherwise
3079     // the new SHL_PARTS operation would need further legalization.
3080     SDValue ShiftOp = N->getOperand(1);
3081     EVT ShiftTy = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
3082     assert(ShiftTy.getScalarSizeInBits() >=
3083            Log2_32_Ceil(VT.getScalarSizeInBits()) &&
3084            "ShiftAmountTy is too small to cover the range of this type!");
3085     if (ShiftOp.getValueType() != ShiftTy)
3086       ShiftOp = DAG.getZExtOrTrunc(ShiftOp, dl, ShiftTy);
3087
3088     SDValue Ops[] = { LHSL, LHSH, ShiftOp };
3089     Lo = DAG.getNode(PartsOpc, dl, DAG.getVTList(VT, VT), Ops);
3090     Hi = Lo.getValue(1);
3091     return;
3092   }
3093
3094   // Otherwise, emit a libcall.
3095   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3096   bool isSigned;
3097   if (N->getOpcode() == ISD::SHL) {
3098     isSigned = false; /*sign irrelevant*/
3099     if (VT == MVT::i16)
3100       LC = RTLIB::SHL_I16;
3101     else if (VT == MVT::i32)
3102       LC = RTLIB::SHL_I32;
3103     else if (VT == MVT::i64)
3104       LC = RTLIB::SHL_I64;
3105     else if (VT == MVT::i128)
3106       LC = RTLIB::SHL_I128;
3107   } else if (N->getOpcode() == ISD::SRL) {
3108     isSigned = false;
3109     if (VT == MVT::i16)
3110       LC = RTLIB::SRL_I16;
3111     else if (VT == MVT::i32)
3112       LC = RTLIB::SRL_I32;
3113     else if (VT == MVT::i64)
3114       LC = RTLIB::SRL_I64;
3115     else if (VT == MVT::i128)
3116       LC = RTLIB::SRL_I128;
3117   } else {
3118     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
3119     isSigned = true;
3120     if (VT == MVT::i16)
3121       LC = RTLIB::SRA_I16;
3122     else if (VT == MVT::i32)
3123       LC = RTLIB::SRA_I32;
3124     else if (VT == MVT::i64)
3125       LC = RTLIB::SRA_I64;
3126     else if (VT == MVT::i128)
3127       LC = RTLIB::SRA_I128;
3128   }
3129
3130   if (LC != RTLIB::UNKNOWN_LIBCALL && TLI.getLibcallName(LC)) {
3131     SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
3132     SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, isSigned, dl).first, Lo, Hi);
3133     return;
3134   }
3135
3136   if (!ExpandShiftWithUnknownAmountBit(N, Lo, Hi))
3137     llvm_unreachable("Unsupported shift!");
3138 }
3139
3140 void DAGTypeLegalizer::ExpandIntRes_SIGN_EXTEND(SDNode *N,
3141                                                 SDValue &Lo, SDValue &Hi) {
3142   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3143   SDLoc dl(N);
3144   SDValue Op = N->getOperand(0);
3145   if (Op.getValueType().bitsLE(NVT)) {
3146     // The low part is sign extension of the input (degenerates to a copy).
3147     Lo = DAG.getNode(ISD::SIGN_EXTEND, dl, NVT, N->getOperand(0));
3148     // The high part is obtained by SRA'ing all but one of the bits of low part.
3149     unsigned LoSize = NVT.getSizeInBits();
3150     Hi = DAG.getNode(
3151         ISD::SRA, dl, NVT, Lo,
3152         DAG.getConstant(LoSize - 1, dl, TLI.getPointerTy(DAG.getDataLayout())));
3153   } else {
3154     // For example, extension of an i48 to an i64.  The operand type necessarily
3155     // promotes to the result type, so will end up being expanded too.
3156     assert(getTypeAction(Op.getValueType()) ==
3157            TargetLowering::TypePromoteInteger &&
3158            "Only know how to promote this result!");
3159     SDValue Res = GetPromotedInteger(Op);
3160     assert(Res.getValueType() == N->getValueType(0) &&
3161            "Operand over promoted?");
3162     // Split the promoted operand.  This will simplify when it is expanded.
3163     SplitInteger(Res, Lo, Hi);
3164     unsigned ExcessBits = Op.getValueSizeInBits() - NVT.getSizeInBits();
3165     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
3166                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
3167                                                         ExcessBits)));
3168   }
3169 }
3170
3171 void DAGTypeLegalizer::
3172 ExpandIntRes_SIGN_EXTEND_INREG(SDNode *N, SDValue &Lo, SDValue &Hi) {
3173   SDLoc dl(N);
3174   GetExpandedInteger(N->getOperand(0), Lo, Hi);
3175   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
3176
3177   if (EVT.bitsLE(Lo.getValueType())) {
3178     // sext_inreg the low part if needed.
3179     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Lo.getValueType(), Lo,
3180                      N->getOperand(1));
3181
3182     // The high part gets the sign extension from the lo-part.  This handles
3183     // things like sextinreg V:i64 from i8.
3184     Hi = DAG.getNode(ISD::SRA, dl, Hi.getValueType(), Lo,
3185                      DAG.getConstant(Hi.getValueSizeInBits() - 1, dl,
3186                                      TLI.getPointerTy(DAG.getDataLayout())));
3187   } else {
3188     // For example, extension of an i48 to an i64.  Leave the low part alone,
3189     // sext_inreg the high part.
3190     unsigned ExcessBits = EVT.getSizeInBits() - Lo.getValueSizeInBits();
3191     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
3192                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
3193                                                         ExcessBits)));
3194   }
3195 }
3196
3197 void DAGTypeLegalizer::ExpandIntRes_SREM(SDNode *N,
3198                                          SDValue &Lo, SDValue &Hi) {
3199   EVT VT = N->getValueType(0);
3200   SDLoc dl(N);
3201   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
3202
3203   if (TLI.getOperationAction(ISD::SDIVREM, VT) == TargetLowering::Custom) {
3204     SDValue Res = DAG.getNode(ISD::SDIVREM, dl, DAG.getVTList(VT, VT), Ops);
3205     SplitInteger(Res.getValue(1), Lo, Hi);
3206     return;
3207   }
3208
3209   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3210   if (VT == MVT::i16)
3211     LC = RTLIB::SREM_I16;
3212   else if (VT == MVT::i32)
3213     LC = RTLIB::SREM_I32;
3214   else if (VT == MVT::i64)
3215     LC = RTLIB::SREM_I64;
3216   else if (VT == MVT::i128)
3217     LC = RTLIB::SREM_I128;
3218   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SREM!");
3219
3220   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true, dl).first, Lo, Hi);
3221 }
3222
3223 void DAGTypeLegalizer::ExpandIntRes_TRUNCATE(SDNode *N,
3224                                              SDValue &Lo, SDValue &Hi) {
3225   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3226   SDLoc dl(N);
3227   Lo = DAG.getNode(ISD::TRUNCATE, dl, NVT, N->getOperand(0));
3228   Hi = DAG.getNode(ISD::SRL, dl, N->getOperand(0).getValueType(),
3229                    N->getOperand(0),
3230                    DAG.getConstant(NVT.getSizeInBits(), dl,
3231                                    TLI.getPointerTy(DAG.getDataLayout())));
3232   Hi = DAG.getNode(ISD::TRUNCATE, dl, NVT, Hi);
3233 }
3234
3235 void DAGTypeLegalizer::ExpandIntRes_XMULO(SDNode *N,
3236                                           SDValue &Lo, SDValue &Hi) {
3237   EVT VT = N->getValueType(0);
3238   SDLoc dl(N);
3239
3240   if (N->getOpcode() == ISD::UMULO) {
3241     // This section expands the operation into the following sequence of
3242     // instructions. `iNh` here refers to a type which has half the bit width of
3243     // the type the original operation operated on.
3244     //
3245     // %0 = %LHS.HI != 0 && %RHS.HI != 0
3246     // %1 = { iNh, i1 } @umul.with.overflow.iNh(iNh %LHS.HI, iNh %RHS.LO)
3247     // %2 = { iNh, i1 } @umul.with.overflow.iNh(iNh %RHS.HI, iNh %LHS.LO)
3248     // %3 = mul nuw iN (%LHS.LOW as iN), (%RHS.LOW as iN)
3249     // %4 = add iN (%1.0 as iN) << Nh, (%2.0 as iN) << Nh
3250     // %5 = { iN, i1 } @uadd.with.overflow.iN( %4, %3 )
3251     //
3252     // %res = { %5.0, %0 || %1.1 || %2.1 || %5.1 }
3253     SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);
3254     SDValue LHSHigh, LHSLow, RHSHigh, RHSLow;
3255     SplitInteger(LHS, LHSLow, LHSHigh);
3256     SplitInteger(RHS, RHSLow, RHSHigh);
3257     EVT HalfVT = LHSLow.getValueType()
3258       , BitVT = N->getValueType(1);
3259     SDVTList VTHalfMulO = DAG.getVTList(HalfVT, BitVT);
3260     SDVTList VTFullAddO = DAG.getVTList(VT, BitVT);
3261
3262     SDValue HalfZero = DAG.getConstant(0, dl, HalfVT);
3263     SDValue Overflow = DAG.getNode(ISD::AND, dl, BitVT,
3264       DAG.getSetCC(dl, BitVT, LHSHigh, HalfZero, ISD::SETNE),
3265       DAG.getSetCC(dl, BitVT, RHSHigh, HalfZero, ISD::SETNE));
3266
3267     SDValue One = DAG.getNode(ISD::UMULO, dl, VTHalfMulO, LHSHigh, RHSLow);
3268     Overflow = DAG.getNode(ISD::OR, dl, BitVT, Overflow, One.getValue(1));
3269     SDValue OneInHigh = DAG.getNode(ISD::BUILD_PAIR, dl, VT, HalfZero,
3270                                     One.getValue(0));
3271
3272     SDValue Two = DAG.getNode(ISD::UMULO, dl, VTHalfMulO, RHSHigh, LHSLow);
3273     Overflow = DAG.getNode(ISD::OR, dl, BitVT, Overflow, Two.getValue(1));
3274     SDValue TwoInHigh = DAG.getNode(ISD::BUILD_PAIR, dl, VT, HalfZero,
3275                                     Two.getValue(0));
3276
3277     // Cannot use `UMUL_LOHI` directly, because some 32-bit targets (ARM) do not
3278     // know how to expand `i64,i64 = umul_lohi a, b` and abort (why isn’t this
3279     // operation recursively legalized?).
3280     //
3281     // Many backends understand this pattern and will convert into LOHI
3282     // themselves, if applicable.
3283     SDValue Three = DAG.getNode(ISD::MUL, dl, VT,
3284       DAG.getNode(ISD::ZERO_EXTEND, dl, VT, LHSLow),
3285       DAG.getNode(ISD::ZERO_EXTEND, dl, VT, RHSLow));
3286     SDValue Four = DAG.getNode(ISD::ADD, dl, VT, OneInHigh, TwoInHigh);
3287     SDValue Five = DAG.getNode(ISD::UADDO, dl, VTFullAddO, Three, Four);
3288     Overflow = DAG.getNode(ISD::OR, dl, BitVT, Overflow, Five.getValue(1));
3289     SplitInteger(Five, Lo, Hi);
3290     ReplaceValueWith(SDValue(N, 1), Overflow);
3291     return;
3292   }
3293
3294   Type *RetTy = VT.getTypeForEVT(*DAG.getContext());
3295   EVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
3296   Type *PtrTy = PtrVT.getTypeForEVT(*DAG.getContext());
3297
3298   // Replace this with a libcall that will check overflow.
3299   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3300   if (VT == MVT::i32)
3301     LC = RTLIB::MULO_I32;
3302   else if (VT == MVT::i64)
3303     LC = RTLIB::MULO_I64;
3304   else if (VT == MVT::i128)
3305     LC = RTLIB::MULO_I128;
3306   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported XMULO!");
3307
3308   SDValue Temp = DAG.CreateStackTemporary(PtrVT);
3309   // Temporary for the overflow value, default it to zero.
3310   SDValue Chain =
3311       DAG.getStore(DAG.getEntryNode(), dl, DAG.getConstant(0, dl, PtrVT), Temp,
3312                    MachinePointerInfo());
3313
3314   TargetLowering::ArgListTy Args;
3315   TargetLowering::ArgListEntry Entry;
3316   for (const SDValue &Op : N->op_values()) {
3317     EVT ArgVT = Op.getValueType();
3318     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
3319     Entry.Node = Op;
3320     Entry.Ty = ArgTy;
3321     Entry.IsSExt = true;
3322     Entry.IsZExt = false;
3323     Args.push_back(Entry);
3324   }
3325
3326   // Also pass the address of the overflow check.
3327   Entry.Node = Temp;
3328   Entry.Ty = PtrTy->getPointerTo();
3329   Entry.IsSExt = true;
3330   Entry.IsZExt = false;
3331   Args.push_back(Entry);
3332
3333   SDValue Func = DAG.getExternalSymbol(TLI.getLibcallName(LC), PtrVT);
3334
3335   TargetLowering::CallLoweringInfo CLI(DAG);
3336   CLI.setDebugLoc(dl)
3337       .setChain(Chain)
3338       .setLibCallee(TLI.getLibcallCallingConv(LC), RetTy, Func, std::move(Args))
3339       .setSExtResult();
3340
3341   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
3342
3343   SplitInteger(CallInfo.first, Lo, Hi);
3344   SDValue Temp2 =
3345       DAG.getLoad(PtrVT, dl, CallInfo.second, Temp, MachinePointerInfo());
3346   SDValue Ofl = DAG.getSetCC(dl, N->getValueType(1), Temp2,
3347                              DAG.getConstant(0, dl, PtrVT),
3348                              ISD::SETNE);
3349   // Use the overflow from the libcall everywhere.
3350   ReplaceValueWith(SDValue(N, 1), Ofl);
3351 }
3352
3353 void DAGTypeLegalizer::ExpandIntRes_UDIV(SDNode *N,
3354                                          SDValue &Lo, SDValue &Hi) {
3355   EVT VT = N->getValueType(0);
3356   SDLoc dl(N);
3357   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
3358
3359   if (TLI.getOperationAction(ISD::UDIVREM, VT) == TargetLowering::Custom) {
3360     SDValue Res = DAG.getNode(ISD::UDIVREM, dl, DAG.getVTList(VT, VT), Ops);
3361     SplitInteger(Res.getValue(0), Lo, Hi);
3362     return;
3363   }
3364
3365   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3366   if (VT == MVT::i16)
3367     LC = RTLIB::UDIV_I16;
3368   else if (VT == MVT::i32)
3369     LC = RTLIB::UDIV_I32;
3370   else if (VT == MVT::i64)
3371     LC = RTLIB::UDIV_I64;
3372   else if (VT == MVT::i128)
3373     LC = RTLIB::UDIV_I128;
3374   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UDIV!");
3375
3376   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, false, dl).first, Lo, Hi);
3377 }
3378
3379 void DAGTypeLegalizer::ExpandIntRes_UREM(SDNode *N,
3380                                          SDValue &Lo, SDValue &Hi) {
3381   EVT VT = N->getValueType(0);
3382   SDLoc dl(N);
3383   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
3384
3385   if (TLI.getOperationAction(ISD::UDIVREM, VT) == TargetLowering::Custom) {
3386     SDValue Res = DAG.getNode(ISD::UDIVREM, dl, DAG.getVTList(VT, VT), Ops);
3387     SplitInteger(Res.getValue(1), Lo, Hi);
3388     return;
3389   }
3390
3391   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3392   if (VT == MVT::i16)
3393     LC = RTLIB::UREM_I16;
3394   else if (VT == MVT::i32)
3395     LC = RTLIB::UREM_I32;
3396   else if (VT == MVT::i64)
3397     LC = RTLIB::UREM_I64;
3398   else if (VT == MVT::i128)
3399     LC = RTLIB::UREM_I128;
3400   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UREM!");
3401
3402   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, false, dl).first, Lo, Hi);
3403 }
3404
3405 void DAGTypeLegalizer::ExpandIntRes_ZERO_EXTEND(SDNode *N,
3406                                                 SDValue &Lo, SDValue &Hi) {
3407   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3408   SDLoc dl(N);
3409   SDValue Op = N->getOperand(0);
3410   if (Op.getValueType().bitsLE(NVT)) {
3411     // The low part is zero extension of the input (degenerates to a copy).
3412     Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, N->getOperand(0));
3413     Hi = DAG.getConstant(0, dl, NVT);   // The high part is just a zero.
3414   } else {
3415     // For example, extension of an i48 to an i64.  The operand type necessarily
3416     // promotes to the result type, so will end up being expanded too.
3417     assert(getTypeAction(Op.getValueType()) ==
3418            TargetLowering::TypePromoteInteger &&
3419            "Only know how to promote this result!");
3420     SDValue Res = GetPromotedInteger(Op);
3421     assert(Res.getValueType() == N->getValueType(0) &&
3422            "Operand over promoted?");
3423     // Split the promoted operand.  This will simplify when it is expanded.
3424     SplitInteger(Res, Lo, Hi);
3425     unsigned ExcessBits = Op.getValueSizeInBits() - NVT.getSizeInBits();
3426     Hi = DAG.getZeroExtendInReg(Hi, dl,
3427                                 EVT::getIntegerVT(*DAG.getContext(),
3428                                                   ExcessBits));
3429   }
3430 }
3431
3432 void DAGTypeLegalizer::ExpandIntRes_ATOMIC_LOAD(SDNode *N,
3433                                                 SDValue &Lo, SDValue &Hi) {
3434   SDLoc dl(N);
3435   EVT VT = cast<AtomicSDNode>(N)->getMemoryVT();
3436   SDVTList VTs = DAG.getVTList(VT, MVT::i1, MVT::Other);
3437   SDValue Zero = DAG.getConstant(0, dl, VT);
3438   SDValue Swap = DAG.getAtomicCmpSwap(
3439       ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS, dl,
3440       cast<AtomicSDNode>(N)->getMemoryVT(), VTs, N->getOperand(0),
3441       N->getOperand(1), Zero, Zero, cast<AtomicSDNode>(N)->getMemOperand());
3442
3443   ReplaceValueWith(SDValue(N, 0), Swap.getValue(0));
3444   ReplaceValueWith(SDValue(N, 1), Swap.getValue(2));
3445 }
3446
3447 void DAGTypeLegalizer::ExpandIntRes_VECREDUCE(SDNode *N,
3448                                               SDValue &Lo, SDValue &Hi) {
3449   // TODO For VECREDUCE_(AND|OR|XOR) we could split the vector and calculate
3450   // both halves independently.
3451   SDValue Res = TLI.expandVecReduce(N, DAG);
3452   SplitInteger(Res, Lo, Hi);
3453 }
3454
3455 //===----------------------------------------------------------------------===//
3456 //  Integer Operand Expansion
3457 //===----------------------------------------------------------------------===//
3458
3459 /// ExpandIntegerOperand - This method is called when the specified operand of
3460 /// the specified node is found to need expansion.  At this point, all of the
3461 /// result types of the node are known to be legal, but other operands of the
3462 /// node may need promotion or expansion as well as the specified one.
3463 bool DAGTypeLegalizer::ExpandIntegerOperand(SDNode *N, unsigned OpNo) {
3464   LLVM_DEBUG(dbgs() << "Expand integer operand: "; N->dump(&DAG);
3465              dbgs() << "\n");
3466   SDValue Res = SDValue();
3467
3468   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
3469     return false;
3470
3471   switch (N->getOpcode()) {
3472   default:
3473   #ifndef NDEBUG
3474     dbgs() << "ExpandIntegerOperand Op #" << OpNo << ": ";
3475     N->dump(&DAG); dbgs() << "\n";
3476   #endif
3477     report_fatal_error("Do not know how to expand this operator's operand!");
3478
3479   case ISD::BITCAST:           Res = ExpandOp_BITCAST(N); break;
3480   case ISD::BR_CC:             Res = ExpandIntOp_BR_CC(N); break;
3481   case ISD::BUILD_VECTOR:      Res = ExpandOp_BUILD_VECTOR(N); break;
3482   case ISD::EXTRACT_ELEMENT:   Res = ExpandOp_EXTRACT_ELEMENT(N); break;
3483   case ISD::INSERT_VECTOR_ELT: Res = ExpandOp_INSERT_VECTOR_ELT(N); break;
3484   case ISD::SCALAR_TO_VECTOR:  Res = ExpandOp_SCALAR_TO_VECTOR(N); break;
3485   case ISD::SELECT_CC:         Res = ExpandIntOp_SELECT_CC(N); break;
3486   case ISD::SETCC:             Res = ExpandIntOp_SETCC(N); break;
3487   case ISD::SETCCCARRY:        Res = ExpandIntOp_SETCCCARRY(N); break;
3488   case ISD::SINT_TO_FP:        Res = ExpandIntOp_SINT_TO_FP(N); break;
3489   case ISD::STORE:   Res = ExpandIntOp_STORE(cast<StoreSDNode>(N), OpNo); break;
3490   case ISD::TRUNCATE:          Res = ExpandIntOp_TRUNCATE(N); break;
3491   case ISD::UINT_TO_FP:        Res = ExpandIntOp_UINT_TO_FP(N); break;
3492
3493   case ISD::SHL:
3494   case ISD::SRA:
3495   case ISD::SRL:
3496   case ISD::ROTL:
3497   case ISD::ROTR:              Res = ExpandIntOp_Shift(N); break;
3498   case ISD::RETURNADDR:
3499   case ISD::FRAMEADDR:         Res = ExpandIntOp_RETURNADDR(N); break;
3500
3501   case ISD::ATOMIC_STORE:      Res = ExpandIntOp_ATOMIC_STORE(N); break;
3502   }
3503
3504   // If the result is null, the sub-method took care of registering results etc.
3505   if (!Res.getNode()) return false;
3506
3507   // If the result is N, the sub-method updated N in place.  Tell the legalizer
3508   // core about this.
3509   if (Res.getNode() == N)
3510     return true;
3511
3512   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
3513          "Invalid operand expansion");
3514
3515   ReplaceValueWith(SDValue(N, 0), Res);
3516   return false;
3517 }
3518
3519 /// IntegerExpandSetCCOperands - Expand the operands of a comparison.  This code
3520 /// is shared among BR_CC, SELECT_CC, and SETCC handlers.
3521 void DAGTypeLegalizer::IntegerExpandSetCCOperands(SDValue &NewLHS,
3522                                                   SDValue &NewRHS,
3523                                                   ISD::CondCode &CCCode,
3524                                                   const SDLoc &dl) {
3525   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
3526   GetExpandedInteger(NewLHS, LHSLo, LHSHi);
3527   GetExpandedInteger(NewRHS, RHSLo, RHSHi);
3528
3529   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
3530     if (RHSLo == RHSHi) {
3531       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) {
3532         if (RHSCST->isAllOnesValue()) {
3533           // Equality comparison to -1.
3534           NewLHS = DAG.getNode(ISD::AND, dl,
3535                                LHSLo.getValueType(), LHSLo, LHSHi);
3536           NewRHS = RHSLo;
3537           return;
3538         }
3539       }
3540     }
3541
3542     NewLHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSLo, RHSLo);
3543     NewRHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSHi, RHSHi);
3544     NewLHS = DAG.getNode(ISD::OR, dl, NewLHS.getValueType(), NewLHS, NewRHS);
3545     NewRHS = DAG.getConstant(0, dl, NewLHS.getValueType());
3546     return;
3547   }
3548
3549   // If this is a comparison of the sign bit, just look at the top part.
3550   // X > -1,  x < 0
3551   if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
3552     if ((CCCode == ISD::SETLT && CST->isNullValue()) ||     // X < 0
3553         (CCCode == ISD::SETGT && CST->isAllOnesValue())) {  // X > -1
3554       NewLHS = LHSHi;
3555       NewRHS = RHSHi;
3556       return;
3557     }
3558
3559   // FIXME: This generated code sucks.
3560   ISD::CondCode LowCC;
3561   switch (CCCode) {
3562   default: llvm_unreachable("Unknown integer setcc!");
3563   case ISD::SETLT:
3564   case ISD::SETULT: LowCC = ISD::SETULT; break;
3565   case ISD::SETGT:
3566   case ISD::SETUGT: LowCC = ISD::SETUGT; break;
3567   case ISD::SETLE:
3568   case ISD::SETULE: LowCC = ISD::SETULE; break;
3569   case ISD::SETGE:
3570   case ISD::SETUGE: LowCC = ISD::SETUGE; break;
3571   }
3572
3573   // LoCmp = lo(op1) < lo(op2)   // Always unsigned comparison
3574   // HiCmp = hi(op1) < hi(op2)   // Signedness depends on operands
3575   // dest  = hi(op1) == hi(op2) ? LoCmp : HiCmp;
3576
3577   // NOTE: on targets without efficient SELECT of bools, we can always use
3578   // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
3579   TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, AfterLegalizeTypes, true,
3580                                                  nullptr);
3581   SDValue LoCmp, HiCmp;
3582   if (TLI.isTypeLegal(LHSLo.getValueType()) &&
3583       TLI.isTypeLegal(RHSLo.getValueType()))
3584     LoCmp = TLI.SimplifySetCC(getSetCCResultType(LHSLo.getValueType()), LHSLo,
3585                               RHSLo, LowCC, false, DagCombineInfo, dl);
3586   if (!LoCmp.getNode())
3587     LoCmp = DAG.getSetCC(dl, getSetCCResultType(LHSLo.getValueType()), LHSLo,
3588                          RHSLo, LowCC);
3589   if (TLI.isTypeLegal(LHSHi.getValueType()) &&
3590       TLI.isTypeLegal(RHSHi.getValueType()))
3591     HiCmp = TLI.SimplifySetCC(getSetCCResultType(LHSHi.getValueType()), LHSHi,
3592                               RHSHi, CCCode, false, DagCombineInfo, dl);
3593   if (!HiCmp.getNode())
3594     HiCmp =
3595         DAG.getNode(ISD::SETCC, dl, getSetCCResultType(LHSHi.getValueType()),
3596                     LHSHi, RHSHi, DAG.getCondCode(CCCode));
3597
3598   ConstantSDNode *LoCmpC = dyn_cast<ConstantSDNode>(LoCmp.getNode());
3599   ConstantSDNode *HiCmpC = dyn_cast<ConstantSDNode>(HiCmp.getNode());
3600
3601   bool EqAllowed = (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
3602                     CCCode == ISD::SETUGE || CCCode == ISD::SETULE);
3603
3604   if ((EqAllowed && (HiCmpC && HiCmpC->isNullValue())) ||
3605       (!EqAllowed && ((HiCmpC && (HiCmpC->getAPIntValue() == 1)) ||
3606                       (LoCmpC && LoCmpC->isNullValue())))) {
3607     // For LE / GE, if high part is known false, ignore the low part.
3608     // For LT / GT: if low part is known false, return the high part.
3609     //              if high part is known true, ignore the low part.
3610     NewLHS = HiCmp;
3611     NewRHS = SDValue();
3612     return;
3613   }
3614
3615   if (LHSHi == RHSHi) {
3616     // Comparing the low bits is enough.
3617     NewLHS = LoCmp;
3618     NewRHS = SDValue();
3619     return;
3620   }
3621
3622   // Lower with SETCCCARRY if the target supports it.
3623   EVT HiVT = LHSHi.getValueType();
3624   EVT ExpandVT = TLI.getTypeToExpandTo(*DAG.getContext(), HiVT);
3625   bool HasSETCCCARRY = TLI.isOperationLegalOrCustom(ISD::SETCCCARRY, ExpandVT);
3626
3627   // FIXME: Make all targets support this, then remove the other lowering.
3628   if (HasSETCCCARRY) {
3629     // SETCCCARRY can detect < and >= directly. For > and <=, flip
3630     // operands and condition code.
3631     bool FlipOperands = false;
3632     switch (CCCode) {
3633     case ISD::SETGT:  CCCode = ISD::SETLT;  FlipOperands = true; break;
3634     case ISD::SETUGT: CCCode = ISD::SETULT; FlipOperands = true; break;
3635     case ISD::SETLE:  CCCode = ISD::SETGE;  FlipOperands = true; break;
3636     case ISD::SETULE: CCCode = ISD::SETUGE; FlipOperands = true; break;
3637     default: break;
3638     }
3639     if (FlipOperands) {
3640       std::swap(LHSLo, RHSLo);
3641       std::swap(LHSHi, RHSHi);
3642     }
3643     // Perform a wide subtraction, feeding the carry from the low part into
3644     // SETCCCARRY. The SETCCCARRY operation is essentially looking at the high
3645     // part of the result of LHS - RHS. It is negative iff LHS < RHS. It is
3646     // zero or positive iff LHS >= RHS.
3647     EVT LoVT = LHSLo.getValueType();
3648     SDVTList VTList = DAG.getVTList(LoVT, getSetCCResultType(LoVT));
3649     SDValue LowCmp = DAG.getNode(ISD::USUBO, dl, VTList, LHSLo, RHSLo);
3650     SDValue Res = DAG.getNode(ISD::SETCCCARRY, dl, getSetCCResultType(HiVT),
3651                               LHSHi, RHSHi, LowCmp.getValue(1),
3652                               DAG.getCondCode(CCCode));
3653     NewLHS = Res;
3654     NewRHS = SDValue();
3655     return;
3656   }
3657
3658   NewLHS = TLI.SimplifySetCC(getSetCCResultType(HiVT), LHSHi, RHSHi, ISD::SETEQ,
3659                              false, DagCombineInfo, dl);
3660   if (!NewLHS.getNode())
3661     NewLHS =
3662         DAG.getSetCC(dl, getSetCCResultType(HiVT), LHSHi, RHSHi, ISD::SETEQ);
3663   NewLHS = DAG.getSelect(dl, LoCmp.getValueType(), NewLHS, LoCmp, HiCmp);
3664   NewRHS = SDValue();
3665 }
3666
3667 SDValue DAGTypeLegalizer::ExpandIntOp_BR_CC(SDNode *N) {
3668   SDValue NewLHS = N->getOperand(2), NewRHS = N->getOperand(3);
3669   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(1))->get();
3670   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
3671
3672   // If ExpandSetCCOperands returned a scalar, we need to compare the result
3673   // against zero to select between true and false values.
3674   if (!NewRHS.getNode()) {
3675     NewRHS = DAG.getConstant(0, SDLoc(N), NewLHS.getValueType());
3676     CCCode = ISD::SETNE;
3677   }
3678
3679   // Update N to have the operands specified.
3680   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
3681                                 DAG.getCondCode(CCCode), NewLHS, NewRHS,
3682                                 N->getOperand(4)), 0);
3683 }
3684
3685 SDValue DAGTypeLegalizer::ExpandIntOp_SELECT_CC(SDNode *N) {
3686   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
3687   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(4))->get();
3688   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
3689
3690   // If ExpandSetCCOperands returned a scalar, we need to compare the result
3691   // against zero to select between true and false values.
3692   if (!NewRHS.getNode()) {
3693     NewRHS = DAG.getConstant(0, SDLoc(N), NewLHS.getValueType());
3694     CCCode = ISD::SETNE;
3695   }
3696
3697   // Update N to have the operands specified.
3698   return SDValue(DAG.UpdateNodeOperands(N, NewLHS, NewRHS,
3699                                 N->getOperand(2), N->getOperand(3),
3700                                 DAG.getCondCode(CCCode)), 0);
3701 }
3702
3703 SDValue DAGTypeLegalizer::ExpandIntOp_SETCC(SDNode *N) {
3704   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
3705   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
3706   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
3707
3708   // If ExpandSetCCOperands returned a scalar, use it.
3709   if (!NewRHS.getNode()) {
3710     assert(NewLHS.getValueType() == N->getValueType(0) &&
3711            "Unexpected setcc expansion!");
3712     return NewLHS;
3713   }
3714
3715   // Otherwise, update N to have the operands specified.
3716   return SDValue(
3717       DAG.UpdateNodeOperands(N, NewLHS, NewRHS, DAG.getCondCode(CCCode)), 0);
3718 }
3719
3720 SDValue DAGTypeLegalizer::ExpandIntOp_SETCCCARRY(SDNode *N) {
3721   SDValue LHS = N->getOperand(0);
3722   SDValue RHS = N->getOperand(1);
3723   SDValue Carry = N->getOperand(2);
3724   SDValue Cond = N->getOperand(3);
3725   SDLoc dl = SDLoc(N);
3726
3727   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
3728   GetExpandedInteger(LHS, LHSLo, LHSHi);
3729   GetExpandedInteger(RHS, RHSLo, RHSHi);
3730
3731   // Expand to a SUBE for the low part and a smaller SETCCCARRY for the high.
3732   SDVTList VTList = DAG.getVTList(LHSLo.getValueType(), Carry.getValueType());
3733   SDValue LowCmp = DAG.getNode(ISD::SUBCARRY, dl, VTList, LHSLo, RHSLo, Carry);
3734   return DAG.getNode(ISD::SETCCCARRY, dl, N->getValueType(0), LHSHi, RHSHi,
3735                      LowCmp.getValue(1), Cond);
3736 }
3737
3738 SDValue DAGTypeLegalizer::ExpandIntOp_Shift(SDNode *N) {
3739   // The value being shifted is legal, but the shift amount is too big.
3740   // It follows that either the result of the shift is undefined, or the
3741   // upper half of the shift amount is zero.  Just use the lower half.
3742   SDValue Lo, Hi;
3743   GetExpandedInteger(N->getOperand(1), Lo, Hi);
3744   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), Lo), 0);
3745 }
3746
3747 SDValue DAGTypeLegalizer::ExpandIntOp_RETURNADDR(SDNode *N) {
3748   // The argument of RETURNADDR / FRAMEADDR builtin is 32 bit contant.  This
3749   // surely makes pretty nice problems on 8/16 bit targets. Just truncate this
3750   // constant to valid type.
3751   SDValue Lo, Hi;
3752   GetExpandedInteger(N->getOperand(0), Lo, Hi);
3753   return SDValue(DAG.UpdateNodeOperands(N, Lo), 0);
3754 }
3755
3756 SDValue DAGTypeLegalizer::ExpandIntOp_SINT_TO_FP(SDNode *N) {
3757   SDValue Op = N->getOperand(0);
3758   EVT DstVT = N->getValueType(0);
3759   RTLIB::Libcall LC = RTLIB::getSINTTOFP(Op.getValueType(), DstVT);
3760   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
3761          "Don't know how to expand this SINT_TO_FP!");
3762   return TLI.makeLibCall(DAG, LC, DstVT, Op, true, SDLoc(N)).first;
3763 }
3764
3765 SDValue DAGTypeLegalizer::ExpandIntOp_STORE(StoreSDNode *N, unsigned OpNo) {
3766   if (ISD::isNormalStore(N))
3767     return ExpandOp_NormalStore(N, OpNo);
3768
3769   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
3770   assert(OpNo == 1 && "Can only expand the stored value so far");
3771
3772   EVT VT = N->getOperand(1).getValueType();
3773   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3774   SDValue Ch  = N->getChain();
3775   SDValue Ptr = N->getBasePtr();
3776   unsigned Alignment = N->getAlignment();
3777   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
3778   AAMDNodes AAInfo = N->getAAInfo();
3779   SDLoc dl(N);
3780   SDValue Lo, Hi;
3781
3782   assert(NVT.isByteSized() && "Expanded type not byte sized!");
3783
3784   if (N->getMemoryVT().bitsLE(NVT)) {
3785     GetExpandedInteger(N->getValue(), Lo, Hi);
3786     return DAG.getTruncStore(Ch, dl, Lo, Ptr, N->getPointerInfo(),
3787                              N->getMemoryVT(), Alignment, MMOFlags, AAInfo);
3788   }
3789
3790   if (DAG.getDataLayout().isLittleEndian()) {
3791     // Little-endian - low bits are at low addresses.
3792     GetExpandedInteger(N->getValue(), Lo, Hi);
3793
3794     Lo = DAG.getStore(Ch, dl, Lo, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
3795                       AAInfo);
3796
3797     unsigned ExcessBits =
3798       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
3799     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
3800
3801     // Increment the pointer to the other half.
3802     unsigned IncrementSize = NVT.getSizeInBits()/8;
3803     Ptr = DAG.getObjectPtrOffset(dl, Ptr, IncrementSize);
3804     Hi = DAG.getTruncStore(
3805         Ch, dl, Hi, Ptr, N->getPointerInfo().getWithOffset(IncrementSize), NEVT,
3806         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
3807     return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
3808   }
3809
3810   // Big-endian - high bits are at low addresses.  Favor aligned stores at
3811   // the cost of some bit-fiddling.
3812   GetExpandedInteger(N->getValue(), Lo, Hi);
3813
3814   EVT ExtVT = N->getMemoryVT();
3815   unsigned EBytes = ExtVT.getStoreSize();
3816   unsigned IncrementSize = NVT.getSizeInBits()/8;
3817   unsigned ExcessBits = (EBytes - IncrementSize)*8;
3818   EVT HiVT = EVT::getIntegerVT(*DAG.getContext(),
3819                                ExtVT.getSizeInBits() - ExcessBits);
3820
3821   if (ExcessBits < NVT.getSizeInBits()) {
3822     // Transfer high bits from the top of Lo to the bottom of Hi.
3823     Hi = DAG.getNode(ISD::SHL, dl, NVT, Hi,
3824                      DAG.getConstant(NVT.getSizeInBits() - ExcessBits, dl,
3825                                      TLI.getPointerTy(DAG.getDataLayout())));
3826     Hi = DAG.getNode(
3827         ISD::OR, dl, NVT, Hi,
3828         DAG.getNode(ISD::SRL, dl, NVT, Lo,
3829                     DAG.getConstant(ExcessBits, dl,
3830                                     TLI.getPointerTy(DAG.getDataLayout()))));
3831   }
3832
3833   // Store both the high bits and maybe some of the low bits.
3834   Hi = DAG.getTruncStore(Ch, dl, Hi, Ptr, N->getPointerInfo(), HiVT, Alignment,
3835                          MMOFlags, AAInfo);
3836
3837   // Increment the pointer to the other half.
3838   Ptr = DAG.getObjectPtrOffset(dl, Ptr, IncrementSize);
3839   // Store the lowest ExcessBits bits in the second half.
3840   Lo = DAG.getTruncStore(Ch, dl, Lo, Ptr,
3841                          N->getPointerInfo().getWithOffset(IncrementSize),
3842                          EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
3843                          MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
3844   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
3845 }
3846
3847 SDValue DAGTypeLegalizer::ExpandIntOp_TRUNCATE(SDNode *N) {
3848   SDValue InL, InH;
3849   GetExpandedInteger(N->getOperand(0), InL, InH);
3850   // Just truncate the low part of the source.
3851   return DAG.getNode(ISD::TRUNCATE, SDLoc(N), N->getValueType(0), InL);
3852 }
3853
3854 SDValue DAGTypeLegalizer::ExpandIntOp_UINT_TO_FP(SDNode *N) {
3855   SDValue Op = N->getOperand(0);
3856   EVT SrcVT = Op.getValueType();
3857   EVT DstVT = N->getValueType(0);
3858   SDLoc dl(N);
3859
3860   // The following optimization is valid only if every value in SrcVT (when
3861   // treated as signed) is representable in DstVT.  Check that the mantissa
3862   // size of DstVT is >= than the number of bits in SrcVT -1.
3863   const fltSemantics &sem = DAG.EVTToAPFloatSemantics(DstVT);
3864   if (APFloat::semanticsPrecision(sem) >= SrcVT.getSizeInBits()-1 &&
3865       TLI.getOperationAction(ISD::SINT_TO_FP, SrcVT) == TargetLowering::Custom){
3866     // Do a signed conversion then adjust the result.
3867     SDValue SignedConv = DAG.getNode(ISD::SINT_TO_FP, dl, DstVT, Op);
3868     SignedConv = TLI.LowerOperation(SignedConv, DAG);
3869
3870     // The result of the signed conversion needs adjusting if the 'sign bit' of
3871     // the incoming integer was set.  To handle this, we dynamically test to see
3872     // if it is set, and, if so, add a fudge factor.
3873
3874     const uint64_t F32TwoE32  = 0x4F800000ULL;
3875     const uint64_t F32TwoE64  = 0x5F800000ULL;
3876     const uint64_t F32TwoE128 = 0x7F800000ULL;
3877
3878     APInt FF(32, 0);
3879     if (SrcVT == MVT::i32)
3880       FF = APInt(32, F32TwoE32);
3881     else if (SrcVT == MVT::i64)
3882       FF = APInt(32, F32TwoE64);
3883     else if (SrcVT == MVT::i128)
3884       FF = APInt(32, F32TwoE128);
3885     else
3886       llvm_unreachable("Unsupported UINT_TO_FP!");
3887
3888     // Check whether the sign bit is set.
3889     SDValue Lo, Hi;
3890     GetExpandedInteger(Op, Lo, Hi);
3891     SDValue SignSet = DAG.getSetCC(dl,
3892                                    getSetCCResultType(Hi.getValueType()),
3893                                    Hi,
3894                                    DAG.getConstant(0, dl, Hi.getValueType()),
3895                                    ISD::SETLT);
3896
3897     // Build a 64 bit pair (0, FF) in the constant pool, with FF in the lo bits.
3898     SDValue FudgePtr =
3899         DAG.getConstantPool(ConstantInt::get(*DAG.getContext(), FF.zext(64)),
3900                             TLI.getPointerTy(DAG.getDataLayout()));
3901
3902     // Get a pointer to FF if the sign bit was set, or to 0 otherwise.
3903     SDValue Zero = DAG.getIntPtrConstant(0, dl);
3904     SDValue Four = DAG.getIntPtrConstant(4, dl);
3905     if (DAG.getDataLayout().isBigEndian())
3906       std::swap(Zero, Four);
3907     SDValue Offset = DAG.getSelect(dl, Zero.getValueType(), SignSet,
3908                                    Zero, Four);
3909     unsigned Alignment = cast<ConstantPoolSDNode>(FudgePtr)->getAlignment();
3910     FudgePtr = DAG.getNode(ISD::ADD, dl, FudgePtr.getValueType(),
3911                            FudgePtr, Offset);
3912     Alignment = std::min(Alignment, 4u);
3913
3914     // Load the value out, extending it from f32 to the destination float type.
3915     // FIXME: Avoid the extend by constructing the right constant pool?
3916     SDValue Fudge = DAG.getExtLoad(
3917         ISD::EXTLOAD, dl, DstVT, DAG.getEntryNode(), FudgePtr,
3918         MachinePointerInfo::getConstantPool(DAG.getMachineFunction()), MVT::f32,
3919         Alignment);
3920     return DAG.getNode(ISD::FADD, dl, DstVT, SignedConv, Fudge);
3921   }
3922
3923   // Otherwise, use a libcall.
3924   RTLIB::Libcall LC = RTLIB::getUINTTOFP(SrcVT, DstVT);
3925   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
3926          "Don't know how to expand this UINT_TO_FP!");
3927   return TLI.makeLibCall(DAG, LC, DstVT, Op, true, dl).first;
3928 }
3929
3930 SDValue DAGTypeLegalizer::ExpandIntOp_ATOMIC_STORE(SDNode *N) {
3931   SDLoc dl(N);
3932   SDValue Swap = DAG.getAtomic(ISD::ATOMIC_SWAP, dl,
3933                                cast<AtomicSDNode>(N)->getMemoryVT(),
3934                                N->getOperand(0),
3935                                N->getOperand(1), N->getOperand(2),
3936                                cast<AtomicSDNode>(N)->getMemOperand());
3937   return Swap.getValue(1);
3938 }
3939
3940
3941 SDValue DAGTypeLegalizer::PromoteIntRes_EXTRACT_SUBVECTOR(SDNode *N) {
3942
3943   EVT OutVT = N->getValueType(0);
3944   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3945   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3946   unsigned OutNumElems = OutVT.getVectorNumElements();
3947   EVT NOutVTElem = NOutVT.getVectorElementType();
3948
3949   SDLoc dl(N);
3950   SDValue BaseIdx = N->getOperand(1);
3951
3952   SDValue InOp0 = N->getOperand(0);
3953   if (getTypeAction(InOp0.getValueType()) == TargetLowering::TypePromoteInteger)
3954     InOp0 = GetPromotedInteger(N->getOperand(0));
3955
3956   EVT InVT = InOp0.getValueType();
3957
3958   SmallVector<SDValue, 8> Ops;
3959   Ops.reserve(OutNumElems);
3960   for (unsigned i = 0; i != OutNumElems; ++i) {
3961
3962     // Extract the element from the original vector.
3963     SDValue Index = DAG.getNode(ISD::ADD, dl, BaseIdx.getValueType(),
3964       BaseIdx, DAG.getConstant(i, dl, BaseIdx.getValueType()));
3965     SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3966       InVT.getVectorElementType(), N->getOperand(0), Index);
3967
3968     SDValue Op = DAG.getAnyExtOrTrunc(Ext, dl, NOutVTElem);
3969     // Insert the converted element to the new vector.
3970     Ops.push_back(Op);
3971   }
3972
3973   return DAG.getBuildVector(NOutVT, dl, Ops);
3974 }
3975
3976
3977 SDValue DAGTypeLegalizer::PromoteIntRes_VECTOR_SHUFFLE(SDNode *N) {
3978   ShuffleVectorSDNode *SV = cast<ShuffleVectorSDNode>(N);
3979   EVT VT = N->getValueType(0);
3980   SDLoc dl(N);
3981
3982   ArrayRef<int> NewMask = SV->getMask().slice(0, VT.getVectorNumElements());
3983
3984   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3985   SDValue V1 = GetPromotedInteger(N->getOperand(1));
3986   EVT OutVT = V0.getValueType();
3987
3988   return DAG.getVectorShuffle(OutVT, dl, V0, V1, NewMask);
3989 }
3990
3991
3992 SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_VECTOR(SDNode *N) {
3993   EVT OutVT = N->getValueType(0);
3994   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3995   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3996   unsigned NumElems = N->getNumOperands();
3997   EVT NOutVTElem = NOutVT.getVectorElementType();
3998
3999   SDLoc dl(N);
4000
4001   SmallVector<SDValue, 8> Ops;
4002   Ops.reserve(NumElems);
4003   for (unsigned i = 0; i != NumElems; ++i) {
4004     SDValue Op;
4005     // BUILD_VECTOR integer operand types are allowed to be larger than the
4006     // result's element type. This may still be true after the promotion. For
4007     // example, we might be promoting (<v?i1> = BV <i32>, <i32>, ...) to
4008     // (v?i16 = BV <i32>, <i32>, ...), and we can't any_extend <i32> to <i16>.
4009     if (N->getOperand(i).getValueType().bitsLT(NOutVTElem))
4010       Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, N->getOperand(i));
4011     else
4012       Op = N->getOperand(i);
4013     Ops.push_back(Op);
4014   }
4015
4016   return DAG.getBuildVector(NOutVT, dl, Ops);
4017 }
4018
4019 SDValue DAGTypeLegalizer::PromoteIntRes_SCALAR_TO_VECTOR(SDNode *N) {
4020
4021   SDLoc dl(N);
4022
4023   assert(!N->getOperand(0).getValueType().isVector() &&
4024          "Input must be a scalar");
4025
4026   EVT OutVT = N->getValueType(0);
4027   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
4028   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
4029   EVT NOutVTElem = NOutVT.getVectorElementType();
4030
4031   SDValue Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, N->getOperand(0));
4032
4033   return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NOutVT, Op);
4034 }
4035
4036 SDValue DAGTypeLegalizer::PromoteIntRes_CONCAT_VECTORS(SDNode *N) {
4037   SDLoc dl(N);
4038
4039   EVT OutVT = N->getValueType(0);
4040   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
4041   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
4042
4043   EVT OutElemTy = NOutVT.getVectorElementType();
4044
4045   unsigned NumElem = N->getOperand(0).getValueType().getVectorNumElements();
4046   unsigned NumOutElem = NOutVT.getVectorNumElements();
4047   unsigned NumOperands = N->getNumOperands();
4048   assert(NumElem * NumOperands == NumOutElem &&
4049          "Unexpected number of elements");
4050
4051   // Take the elements from the first vector.
4052   SmallVector<SDValue, 8> Ops(NumOutElem);
4053   for (unsigned i = 0; i < NumOperands; ++i) {
4054     SDValue Op = N->getOperand(i);
4055     if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteInteger)
4056       Op = GetPromotedInteger(Op);
4057     EVT SclrTy = Op.getValueType().getVectorElementType();
4058     assert(NumElem == Op.getValueType().getVectorNumElements() &&
4059            "Unexpected number of elements");
4060
4061     for (unsigned j = 0; j < NumElem; ++j) {
4062       SDValue Ext = DAG.getNode(
4063           ISD::EXTRACT_VECTOR_ELT, dl, SclrTy, Op,
4064           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4065       Ops[i * NumElem + j] = DAG.getAnyExtOrTrunc(Ext, dl, OutElemTy);
4066     }
4067   }
4068
4069   return DAG.getBuildVector(NOutVT, dl, Ops);
4070 }
4071
4072 SDValue DAGTypeLegalizer::PromoteIntRes_EXTEND_VECTOR_INREG(SDNode *N) {
4073   EVT VT = N->getValueType(0);
4074   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4075   assert(NVT.isVector() && "This type must be promoted to a vector type");
4076
4077   SDLoc dl(N);
4078
4079   // For operands whose TypeAction is to promote, extend the promoted node
4080   // appropriately (ZERO_EXTEND or SIGN_EXTEND) from the original pre-promotion
4081   // type, and then construct a new *_EXTEND_VECTOR_INREG node to the promote-to
4082   // type..
4083   if (getTypeAction(N->getOperand(0).getValueType())
4084       == TargetLowering::TypePromoteInteger) {
4085     SDValue Promoted;
4086
4087     switch(N->getOpcode()) {
4088       case ISD::SIGN_EXTEND_VECTOR_INREG:
4089         Promoted = SExtPromotedInteger(N->getOperand(0));
4090         break;
4091       case ISD::ZERO_EXTEND_VECTOR_INREG:
4092         Promoted = ZExtPromotedInteger(N->getOperand(0));
4093         break;
4094       case ISD::ANY_EXTEND_VECTOR_INREG:
4095         Promoted = GetPromotedInteger(N->getOperand(0));
4096         break;
4097       default:
4098         llvm_unreachable("Node has unexpected Opcode");
4099     }
4100     return DAG.getNode(N->getOpcode(), dl, NVT, Promoted);
4101   }
4102
4103   // Directly extend to the appropriate transform-to type.
4104   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
4105 }
4106
4107 SDValue DAGTypeLegalizer::PromoteIntRes_INSERT_VECTOR_ELT(SDNode *N) {
4108   EVT OutVT = N->getValueType(0);
4109   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
4110   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
4111
4112   EVT NOutVTElem = NOutVT.getVectorElementType();
4113
4114   SDLoc dl(N);
4115   SDValue V0 = GetPromotedInteger(N->getOperand(0));
4116
4117   SDValue ConvElem = DAG.getNode(ISD::ANY_EXTEND, dl,
4118     NOutVTElem, N->getOperand(1));
4119   return DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NOutVT,
4120     V0, ConvElem, N->getOperand(2));
4121 }
4122
4123 SDValue DAGTypeLegalizer::PromoteIntRes_VECREDUCE(SDNode *N) {
4124   // The VECREDUCE result size may be larger than the element size, so
4125   // we can simply change the result type.
4126   SDLoc dl(N);
4127   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
4128   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
4129 }
4130
4131 SDValue DAGTypeLegalizer::PromoteIntOp_EXTRACT_VECTOR_ELT(SDNode *N) {
4132   SDLoc dl(N);
4133   SDValue V0 = GetPromotedInteger(N->getOperand(0));
4134   SDValue V1 = DAG.getZExtOrTrunc(N->getOperand(1), dl,
4135                                   TLI.getVectorIdxTy(DAG.getDataLayout()));
4136   SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
4137     V0->getValueType(0).getScalarType(), V0, V1);
4138
4139   // EXTRACT_VECTOR_ELT can return types which are wider than the incoming
4140   // element types. If this is the case then we need to expand the outgoing
4141   // value and not truncate it.
4142   return DAG.getAnyExtOrTrunc(Ext, dl, N->getValueType(0));
4143 }
4144
4145 SDValue DAGTypeLegalizer::PromoteIntOp_EXTRACT_SUBVECTOR(SDNode *N) {
4146   SDLoc dl(N);
4147   SDValue V0 = GetPromotedInteger(N->getOperand(0));
4148   MVT InVT = V0.getValueType().getSimpleVT();
4149   MVT OutVT = MVT::getVectorVT(InVT.getVectorElementType(),
4150                                N->getValueType(0).getVectorNumElements());
4151   SDValue Ext = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, OutVT, V0, N->getOperand(1));
4152   return DAG.getNode(ISD::TRUNCATE, dl, N->getValueType(0), Ext);
4153 }
4154
4155 SDValue DAGTypeLegalizer::PromoteIntOp_CONCAT_VECTORS(SDNode *N) {
4156   SDLoc dl(N);
4157   unsigned NumElems = N->getNumOperands();
4158
4159   EVT RetSclrTy = N->getValueType(0).getVectorElementType();
4160
4161   SmallVector<SDValue, 8> NewOps;
4162   NewOps.reserve(NumElems);
4163
4164   // For each incoming vector
4165   for (unsigned VecIdx = 0; VecIdx != NumElems; ++VecIdx) {
4166     SDValue Incoming = GetPromotedInteger(N->getOperand(VecIdx));
4167     EVT SclrTy = Incoming->getValueType(0).getVectorElementType();
4168     unsigned NumElem = Incoming->getValueType(0).getVectorNumElements();
4169
4170     for (unsigned i=0; i<NumElem; ++i) {
4171       // Extract element from incoming vector
4172       SDValue Ex = DAG.getNode(
4173           ISD::EXTRACT_VECTOR_ELT, dl, SclrTy, Incoming,
4174           DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4175       SDValue Tr = DAG.getNode(ISD::TRUNCATE, dl, RetSclrTy, Ex);
4176       NewOps.push_back(Tr);
4177     }
4178   }
4179
4180   return DAG.getBuildVector(N->getValueType(0), dl, NewOps);
4181 }