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