lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

   1 //===------- LegalizeVectorTypes.cpp - Legalization of vector types -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file performs vector type splitting and scalarization for LegalizeTypes.
  11 // Scalarization is the act of changing a computation in an illegal one-element
  12 // vector type to be a computation in its scalar element type.  For example,
  13 // implementing <1 x f32> arithmetic in a scalar f32 register.  This is needed
  14 // as a base case when scalarizing vector arithmetic like <4 x f32>, which
  15 // eventually decomposes to scalars if the target doesn't support v4f32 or v2f32
  16 // types.
  17 // Splitting is the act of changing a computation in an invalid vector type to
  18 // be a computation in two vectors of half the size.  For example, implementing
  19 // <128 x f32> operations in terms of two <64 x f32> operations.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "LegalizeTypes.h"
  24 #include "llvm/IR/DataLayout.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "legalize-types"
  30
  31 //===----------------------------------------------------------------------===//
  32 //  Result Vector Scalarization: <1 x ty> -> ty.
  33 //===----------------------------------------------------------------------===//
  34
  35 void DAGTypeLegalizer::ScalarizeVectorResult(SDNode *N, unsigned ResNo) {
  36   DEBUG(dbgs() << "Scalarize node result " << ResNo << ": ";
  37         N->dump(&DAG);
  38         dbgs() << "\n");
  39   SDValue R = SDValue();
  40
  41   switch (N->getOpcode()) {
  42   default:
  43 #ifndef NDEBUG
  44     dbgs() << "ScalarizeVectorResult #" << ResNo << ": ";
  45     N->dump(&DAG);
  46     dbgs() << "\n";
  47 #endif
  48     report_fatal_error("Do not know how to scalarize the result of this "
  49                        "operator!\n");
  50
  51   case ISD::MERGE_VALUES:      R = ScalarizeVecRes_MERGE_VALUES(N, ResNo);break;
  52   case ISD::BITCAST:           R = ScalarizeVecRes_BITCAST(N); break;
  53   case ISD::BUILD_VECTOR:      R = ScalarizeVecRes_BUILD_VECTOR(N); break;
  54   case ISD::EXTRACT_SUBVECTOR: R = ScalarizeVecRes_EXTRACT_SUBVECTOR(N); break;
  55   case ISD::FP_ROUND:          R = ScalarizeVecRes_FP_ROUND(N); break;
  56   case ISD::FP_ROUND_INREG:    R = ScalarizeVecRes_InregOp(N); break;
  57   case ISD::FPOWI:             R = ScalarizeVecRes_FPOWI(N); break;
  58   case ISD::INSERT_VECTOR_ELT: R = ScalarizeVecRes_INSERT_VECTOR_ELT(N); break;
  59   case ISD::LOAD:           R = ScalarizeVecRes_LOAD(cast<LoadSDNode>(N));break;
  60   case ISD::SCALAR_TO_VECTOR:  R = ScalarizeVecRes_SCALAR_TO_VECTOR(N); break;
  61   case ISD::SIGN_EXTEND_INREG: R = ScalarizeVecRes_InregOp(N); break;
  62   case ISD::VSELECT:           R = ScalarizeVecRes_VSELECT(N); break;
  63   case ISD::SELECT:            R = ScalarizeVecRes_SELECT(N); break;
  64   case ISD::SELECT_CC:         R = ScalarizeVecRes_SELECT_CC(N); break;
  65   case ISD::SETCC:             R = ScalarizeVecRes_SETCC(N); break;
  66   case ISD::UNDEF:             R = ScalarizeVecRes_UNDEF(N); break;
  67   case ISD::VECTOR_SHUFFLE:    R = ScalarizeVecRes_VECTOR_SHUFFLE(N); break;
  68   case ISD::ANY_EXTEND_VECTOR_INREG:
  69   case ISD::SIGN_EXTEND_VECTOR_INREG:
  70   case ISD::ZERO_EXTEND_VECTOR_INREG:
  71     R = ScalarizeVecRes_VecInregOp(N);
  72     break;
  73   case ISD::ANY_EXTEND:
  74   case ISD::BITREVERSE:
  75   case ISD::BSWAP:
  76   case ISD::CTLZ:
  77   case ISD::CTLZ_ZERO_UNDEF:
  78   case ISD::CTPOP:
  79   case ISD::CTTZ:
  80   case ISD::CTTZ_ZERO_UNDEF:
  81   case ISD::FABS:
  82   case ISD::FCEIL:
  83   case ISD::FCOS:
  84   case ISD::FEXP:
  85   case ISD::FEXP2:
  86   case ISD::FFLOOR:
  87   case ISD::FLOG:
  88   case ISD::FLOG10:
  89   case ISD::FLOG2:
  90   case ISD::FNEARBYINT:
  91   case ISD::FNEG:
  92   case ISD::FP_EXTEND:
  93   case ISD::FP_TO_SINT:
  94   case ISD::FP_TO_UINT:
  95   case ISD::FRINT:
  96   case ISD::FROUND:
  97   case ISD::FSIN:
  98   case ISD::FSQRT:
  99   case ISD::FTRUNC:
 100   case ISD::SIGN_EXTEND:
 101   case ISD::SINT_TO_FP:
 102   case ISD::TRUNCATE:
 103   case ISD::UINT_TO_FP:
 104   case ISD::ZERO_EXTEND:
 105   case ISD::FCANONICALIZE:
 106     R = ScalarizeVecRes_UnaryOp(N);
 107     break;
 108
 109   case ISD::ADD:
 110   case ISD::AND:
 111   case ISD::FADD:
 112   case ISD::FCOPYSIGN:
 113   case ISD::FDIV:
 114   case ISD::FMUL:
 115   case ISD::FMINNUM:
 116   case ISD::FMAXNUM:
 117   case ISD::FMINNAN:
 118   case ISD::FMAXNAN:
 119   case ISD::SMIN:
 120   case ISD::SMAX:
 121   case ISD::UMIN:
 122   case ISD::UMAX:
 123
 124   case ISD::FPOW:
 125   case ISD::FREM:
 126   case ISD::FSUB:
 127   case ISD::MUL:
 128   case ISD::OR:
 129   case ISD::SDIV:
 130   case ISD::SREM:
 131   case ISD::SUB:
 132   case ISD::UDIV:
 133   case ISD::UREM:
 134   case ISD::XOR:
 135   case ISD::SHL:
 136   case ISD::SRA:
 137   case ISD::SRL:
 138     R = ScalarizeVecRes_BinOp(N);
 139     break;
 140   case ISD::FMA:
 141     R = ScalarizeVecRes_TernaryOp(N);
 142     break;
 143   }
 144
 145   // If R is null, the sub-method took care of registering the result.
 146   if (R.getNode())
 147     SetScalarizedVector(SDValue(N, ResNo), R);
 148 }
 149
 150 SDValue DAGTypeLegalizer::ScalarizeVecRes_BinOp(SDNode *N) {
 151   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 152   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 153   return DAG.getNode(N->getOpcode(), SDLoc(N),
 154                      LHS.getValueType(), LHS, RHS, N->getFlags());
 155 }
 156
 157 SDValue DAGTypeLegalizer::ScalarizeVecRes_TernaryOp(SDNode *N) {
 158   SDValue Op0 = GetScalarizedVector(N->getOperand(0));
 159   SDValue Op1 = GetScalarizedVector(N->getOperand(1));
 160   SDValue Op2 = GetScalarizedVector(N->getOperand(2));
 161   return DAG.getNode(N->getOpcode(), SDLoc(N),
 162                      Op0.getValueType(), Op0, Op1, Op2);
 163 }
 164
 165 SDValue DAGTypeLegalizer::ScalarizeVecRes_MERGE_VALUES(SDNode *N,
 166                                                        unsigned ResNo) {
 167   SDValue Op = DisintegrateMERGE_VALUES(N, ResNo);
 168   return GetScalarizedVector(Op);
 169 }
 170
 171 SDValue DAGTypeLegalizer::ScalarizeVecRes_BITCAST(SDNode *N) {
 172   SDValue Op = N->getOperand(0);
 173   if (Op.getValueType().isVector()
 174       && Op.getValueType().getVectorNumElements() == 1
 175       && !isSimpleLegalType(Op.getValueType()))
 176     Op = GetScalarizedVector(Op);
 177   EVT NewVT = N->getValueType(0).getVectorElementType();
 178   return DAG.getNode(ISD::BITCAST, SDLoc(N),
 179                      NewVT, Op);
 180 }
 181
 182 SDValue DAGTypeLegalizer::ScalarizeVecRes_BUILD_VECTOR(SDNode *N) {
 183   EVT EltVT = N->getValueType(0).getVectorElementType();
 184   SDValue InOp = N->getOperand(0);
 185   // The BUILD_VECTOR operands may be of wider element types and
 186   // we may need to truncate them back to the requested return type.
 187   if (EltVT.isInteger())
 188     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
 189   return InOp;
 190 }
 191
 192 SDValue DAGTypeLegalizer::ScalarizeVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
 193   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
 194                      N->getValueType(0).getVectorElementType(),
 195                      N->getOperand(0), N->getOperand(1));
 196 }
 197
 198 SDValue DAGTypeLegalizer::ScalarizeVecRes_FP_ROUND(SDNode *N) {
 199   EVT NewVT = N->getValueType(0).getVectorElementType();
 200   SDValue Op = GetScalarizedVector(N->getOperand(0));
 201   return DAG.getNode(ISD::FP_ROUND, SDLoc(N),
 202                      NewVT, Op, N->getOperand(1));
 203 }
 204
 205 SDValue DAGTypeLegalizer::ScalarizeVecRes_FPOWI(SDNode *N) {
 206   SDValue Op = GetScalarizedVector(N->getOperand(0));
 207   return DAG.getNode(ISD::FPOWI, SDLoc(N),
 208                      Op.getValueType(), Op, N->getOperand(1));
 209 }
 210
 211 SDValue DAGTypeLegalizer::ScalarizeVecRes_INSERT_VECTOR_ELT(SDNode *N) {
 212   // The value to insert may have a wider type than the vector element type,
 213   // so be sure to truncate it to the element type if necessary.
 214   SDValue Op = N->getOperand(1);
 215   EVT EltVT = N->getValueType(0).getVectorElementType();
 216   if (Op.getValueType() != EltVT)
 217     // FIXME: Can this happen for floating point types?
 218     Op = DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, Op);
 219   return Op;
 220 }
 221
 222 SDValue DAGTypeLegalizer::ScalarizeVecRes_LOAD(LoadSDNode *N) {
 223   assert(N->isUnindexed() && "Indexed vector load?");
 224
 225   SDValue Result = DAG.getLoad(
 226       ISD::UNINDEXED, N->getExtensionType(),
 227       N->getValueType(0).getVectorElementType(), SDLoc(N), N->getChain(),
 228       N->getBasePtr(), DAG.getUNDEF(N->getBasePtr().getValueType()),
 229       N->getPointerInfo(), N->getMemoryVT().getVectorElementType(),
 230       N->getOriginalAlignment(), N->getMemOperand()->getFlags(),
 231       N->getAAInfo());
 232
 233   // Legalize the chain result - switch anything that used the old chain to
 234   // use the new one.
 235   ReplaceValueWith(SDValue(N, 1), Result.getValue(1));
 236   return Result;
 237 }
 238
 239 SDValue DAGTypeLegalizer::ScalarizeVecRes_UnaryOp(SDNode *N) {
 240   // Get the dest type - it doesn't always match the input type, e.g. int_to_fp.
 241   EVT DestVT = N->getValueType(0).getVectorElementType();
 242   SDValue Op = N->getOperand(0);
 243   EVT OpVT = Op.getValueType();
 244   SDLoc DL(N);
 245   // The result needs scalarizing, but it's not a given that the source does.
 246   // This is a workaround for targets where it's impossible to scalarize the
 247   // result of a conversion, because the source type is legal.
 248   // For instance, this happens on AArch64: v1i1 is illegal but v1i{8,16,32}
 249   // are widened to v8i8, v4i16, and v2i32, which is legal, because v1i64 is
 250   // legal and was not scalarized.
 251   // See the similar logic in ScalarizeVecRes_SETCC
 252   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
 253     Op = GetScalarizedVector(Op);
 254   } else {
 255     EVT VT = OpVT.getVectorElementType();
 256     Op = DAG.getNode(
 257         ISD::EXTRACT_VECTOR_ELT, DL, VT, Op,
 258         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
 259   }
 260   return DAG.getNode(N->getOpcode(), SDLoc(N), DestVT, Op);
 261 }
 262
 263 SDValue DAGTypeLegalizer::ScalarizeVecRes_InregOp(SDNode *N) {
 264   EVT EltVT = N->getValueType(0).getVectorElementType();
 265   EVT ExtVT = cast<VTSDNode>(N->getOperand(1))->getVT().getVectorElementType();
 266   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 267   return DAG.getNode(N->getOpcode(), SDLoc(N), EltVT,
 268                      LHS, DAG.getValueType(ExtVT));
 269 }
 270
 271 SDValue DAGTypeLegalizer::ScalarizeVecRes_VecInregOp(SDNode *N) {
 272   SDLoc DL(N);
 273   SDValue Op = N->getOperand(0);
 274
 275   EVT OpVT = Op.getValueType();
 276   EVT OpEltVT = OpVT.getVectorElementType();
 277   EVT EltVT = N->getValueType(0).getVectorElementType();
 278
 279   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
 280     Op = GetScalarizedVector(Op);
 281   } else {
 282     Op = DAG.getNode(
 283         ISD::EXTRACT_VECTOR_ELT, DL, OpEltVT, Op,
 284         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
 285   }
 286
 287   switch (N->getOpcode()) {
 288   case ISD::ANY_EXTEND_VECTOR_INREG:
 289     return DAG.getNode(ISD::ANY_EXTEND, DL, EltVT, Op);
 290   case ISD::SIGN_EXTEND_VECTOR_INREG:
 291     return DAG.getNode(ISD::SIGN_EXTEND, DL, EltVT, Op);
 292   case ISD::ZERO_EXTEND_VECTOR_INREG:
 293     return DAG.getNode(ISD::ZERO_EXTEND, DL, EltVT, Op);
 294   }
 295
 296   llvm_unreachable("Illegal extend_vector_inreg opcode");
 297 }
 298
 299 SDValue DAGTypeLegalizer::ScalarizeVecRes_SCALAR_TO_VECTOR(SDNode *N) {
 300   // If the operand is wider than the vector element type then it is implicitly
 301   // truncated.  Make that explicit here.
 302   EVT EltVT = N->getValueType(0).getVectorElementType();
 303   SDValue InOp = N->getOperand(0);
 304   if (InOp.getValueType() != EltVT)
 305     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
 306   return InOp;
 307 }
 308
 309 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSELECT(SDNode *N) {
 310   SDValue Cond = N->getOperand(0);
 311   EVT OpVT = Cond.getValueType();
 312   SDLoc DL(N);
 313   // The vselect result and true/value operands needs scalarizing, but it's
 314   // not a given that the Cond does. For instance, in AVX512 v1i1 is legal.
 315   // See the similar logic in ScalarizeVecRes_SETCC
 316   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
 317     Cond = GetScalarizedVector(Cond);
 318   } else {
 319     EVT VT = OpVT.getVectorElementType();
 320     Cond = DAG.getNode(
 321         ISD::EXTRACT_VECTOR_ELT, DL, VT, Cond,
 322         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
 323   }
 324
 325   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 326   TargetLowering::BooleanContent ScalarBool =
 327       TLI.getBooleanContents(false, false);
 328   TargetLowering::BooleanContent VecBool = TLI.getBooleanContents(true, false);
 329
 330   // If integer and float booleans have different contents then we can't
 331   // reliably optimize in all cases. There is a full explanation for this in
 332   // DAGCombiner::visitSELECT() where the same issue affects folding
 333   // (select C, 0, 1) to (xor C, 1).
 334   if (TLI.getBooleanContents(false, false) !=
 335       TLI.getBooleanContents(false, true)) {
 336     // At least try the common case where the boolean is generated by a
 337     // comparison.
 338     if (Cond->getOpcode() == ISD::SETCC) {
 339       EVT OpVT = Cond->getOperand(0).getValueType();
 340       ScalarBool = TLI.getBooleanContents(OpVT.getScalarType());
 341       VecBool = TLI.getBooleanContents(OpVT);
 342     } else
 343       ScalarBool = TargetLowering::UndefinedBooleanContent;
 344   }
 345
 346   EVT CondVT = Cond.getValueType();
 347   if (ScalarBool != VecBool) {
 348     switch (ScalarBool) {
 349       case TargetLowering::UndefinedBooleanContent:
 350         break;
 351       case TargetLowering::ZeroOrOneBooleanContent:
 352         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
 353                VecBool == TargetLowering::ZeroOrNegativeOneBooleanContent);
 354         // Vector read from all ones, scalar expects a single 1 so mask.
 355         Cond = DAG.getNode(ISD::AND, SDLoc(N), CondVT,
 356                            Cond, DAG.getConstant(1, SDLoc(N), CondVT));
 357         break;
 358       case TargetLowering::ZeroOrNegativeOneBooleanContent:
 359         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
 360                VecBool == TargetLowering::ZeroOrOneBooleanContent);
 361         // Vector reads from a one, scalar from all ones so sign extend.
 362         Cond = DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N), CondVT,
 363                            Cond, DAG.getValueType(MVT::i1));
 364         break;
 365     }
 366   }
 367
 368   // Truncate the condition if needed
 369   auto BoolVT = getSetCCResultType(CondVT);
 370   if (BoolVT.bitsLT(CondVT))
 371     Cond = DAG.getNode(ISD::TRUNCATE, SDLoc(N), BoolVT, Cond);
 372
 373   return DAG.getSelect(SDLoc(N),
 374                        LHS.getValueType(), Cond, LHS,
 375                        GetScalarizedVector(N->getOperand(2)));
 376 }
 377
 378 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT(SDNode *N) {
 379   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 380   return DAG.getSelect(SDLoc(N),
 381                        LHS.getValueType(), N->getOperand(0), LHS,
 382                        GetScalarizedVector(N->getOperand(2)));
 383 }
 384
 385 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT_CC(SDNode *N) {
 386   SDValue LHS = GetScalarizedVector(N->getOperand(2));
 387   return DAG.getNode(ISD::SELECT_CC, SDLoc(N), LHS.getValueType(),
 388                      N->getOperand(0), N->getOperand(1),
 389                      LHS, GetScalarizedVector(N->getOperand(3)),
 390                      N->getOperand(4));
 391 }
 392
 393 SDValue DAGTypeLegalizer::ScalarizeVecRes_UNDEF(SDNode *N) {
 394   return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
 395 }
 396
 397 SDValue DAGTypeLegalizer::ScalarizeVecRes_VECTOR_SHUFFLE(SDNode *N) {
 398   // Figure out if the scalar is the LHS or RHS and return it.
 399   SDValue Arg = N->getOperand(2).getOperand(0);
 400   if (Arg.isUndef())
 401     return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
 402   unsigned Op = !cast<ConstantSDNode>(Arg)->isNullValue();
 403   return GetScalarizedVector(N->getOperand(Op));
 404 }
 405
 406 SDValue DAGTypeLegalizer::ScalarizeVecRes_SETCC(SDNode *N) {
 407   assert(N->getValueType(0).isVector() &&
 408          N->getOperand(0).getValueType().isVector() &&
 409          "Operand types must be vectors");
 410   SDValue LHS = N->getOperand(0);
 411   SDValue RHS = N->getOperand(1);
 412   EVT OpVT = LHS.getValueType();
 413   EVT NVT = N->getValueType(0).getVectorElementType();
 414   SDLoc DL(N);
 415
 416   // The result needs scalarizing, but it's not a given that the source does.
 417   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
 418     LHS = GetScalarizedVector(LHS);
 419     RHS = GetScalarizedVector(RHS);
 420   } else {
 421     EVT VT = OpVT.getVectorElementType();
 422     LHS = DAG.getNode(
 423         ISD::EXTRACT_VECTOR_ELT, DL, VT, LHS,
 424         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
 425     RHS = DAG.getNode(
 426         ISD::EXTRACT_VECTOR_ELT, DL, VT, RHS,
 427         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
 428   }
 429
 430   // Turn it into a scalar SETCC.
 431   SDValue Res = DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS,
 432                             N->getOperand(2));
 433   // Vectors may have a different boolean contents to scalars.  Promote the
 434   // value appropriately.
 435   ISD::NodeType ExtendCode =
 436       TargetLowering::getExtendForContent(TLI.getBooleanContents(OpVT));
 437   return DAG.getNode(ExtendCode, DL, NVT, Res);
 438 }
 439
 440
 441 //===----------------------------------------------------------------------===//
 442 //  Operand Vector Scalarization <1 x ty> -> ty.
 443 //===----------------------------------------------------------------------===//
 444
 445 bool DAGTypeLegalizer::ScalarizeVectorOperand(SDNode *N, unsigned OpNo) {
 446   DEBUG(dbgs() << "Scalarize node operand " << OpNo << ": ";
 447         N->dump(&DAG);
 448         dbgs() << "\n");
 449   SDValue Res = SDValue();
 450
 451   if (!Res.getNode()) {
 452     switch (N->getOpcode()) {
 453     default:
 454 #ifndef NDEBUG
 455       dbgs() << "ScalarizeVectorOperand Op #" << OpNo << ": ";
 456       N->dump(&DAG);
 457       dbgs() << "\n";
 458 #endif
 459       report_fatal_error("Do not know how to scalarize this operator's "
 460                          "operand!\n");
 461     case ISD::BITCAST:
 462       Res = ScalarizeVecOp_BITCAST(N);
 463       break;
 464     case ISD::ANY_EXTEND:
 465     case ISD::ZERO_EXTEND:
 466     case ISD::SIGN_EXTEND:
 467     case ISD::TRUNCATE:
 468     case ISD::FP_TO_SINT:
 469     case ISD::FP_TO_UINT:
 470     case ISD::SINT_TO_FP:
 471     case ISD::UINT_TO_FP:
 472       Res = ScalarizeVecOp_UnaryOp(N);
 473       break;
 474     case ISD::CONCAT_VECTORS:
 475       Res = ScalarizeVecOp_CONCAT_VECTORS(N);
 476       break;
 477     case ISD::EXTRACT_VECTOR_ELT:
 478       Res = ScalarizeVecOp_EXTRACT_VECTOR_ELT(N);
 479       break;
 480     case ISD::VSELECT:
 481       Res = ScalarizeVecOp_VSELECT(N);
 482       break;
 483     case ISD::SETCC:
 484       Res = ScalarizeVecOp_VSETCC(N);
 485       break;
 486     case ISD::STORE:
 487       Res = ScalarizeVecOp_STORE(cast<StoreSDNode>(N), OpNo);
 488       break;
 489     case ISD::FP_ROUND:
 490       Res = ScalarizeVecOp_FP_ROUND(N, OpNo);
 491       break;
 492     }
 493   }
 494
 495   // If the result is null, the sub-method took care of registering results etc.
 496   if (!Res.getNode()) return false;
 497
 498   // If the result is N, the sub-method updated N in place.  Tell the legalizer
 499   // core about this.
 500   if (Res.getNode() == N)
 501     return true;
 502
 503   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 504          "Invalid operand expansion");
 505
 506   ReplaceValueWith(SDValue(N, 0), Res);
 507   return false;
 508 }
 509
 510 /// If the value to convert is a vector that needs to be scalarized, it must be
 511 /// <1 x ty>. Convert the element instead.
 512 SDValue DAGTypeLegalizer::ScalarizeVecOp_BITCAST(SDNode *N) {
 513   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 514   return DAG.getNode(ISD::BITCAST, SDLoc(N),
 515                      N->getValueType(0), Elt);
 516 }
 517
 518 /// If the input is a vector that needs to be scalarized, it must be <1 x ty>.
 519 /// Do the operation on the element instead.
 520 SDValue DAGTypeLegalizer::ScalarizeVecOp_UnaryOp(SDNode *N) {
 521   assert(N->getValueType(0).getVectorNumElements() == 1 &&
 522          "Unexpected vector type!");
 523   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 524   SDValue Op = DAG.getNode(N->getOpcode(), SDLoc(N),
 525                            N->getValueType(0).getScalarType(), Elt);
 526   // Revectorize the result so the types line up with what the uses of this
 527   // expression expect.
 528   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N), N->getValueType(0), Op);
 529 }
 530
 531 /// The vectors to concatenate have length one - use a BUILD_VECTOR instead.
 532 SDValue DAGTypeLegalizer::ScalarizeVecOp_CONCAT_VECTORS(SDNode *N) {
 533   SmallVector<SDValue, 8> Ops(N->getNumOperands());
 534   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i)
 535     Ops[i] = GetScalarizedVector(N->getOperand(i));
 536   return DAG.getBuildVector(N->getValueType(0), SDLoc(N), Ops);
 537 }
 538
 539 /// If the input is a vector that needs to be scalarized, it must be <1 x ty>,
 540 /// so just return the element, ignoring the index.
 541 SDValue DAGTypeLegalizer::ScalarizeVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
 542   EVT VT = N->getValueType(0);
 543   SDValue Res = GetScalarizedVector(N->getOperand(0));
 544   if (Res.getValueType() != VT)
 545     Res = VT.isFloatingPoint()
 546               ? DAG.getNode(ISD::FP_EXTEND, SDLoc(N), VT, Res)
 547               : DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), VT, Res);
 548   return Res;
 549 }
 550
 551 /// If the input condition is a vector that needs to be scalarized, it must be
 552 /// <1 x i1>, so just convert to a normal ISD::SELECT
 553 /// (still with vector output type since that was acceptable if we got here).
 554 SDValue DAGTypeLegalizer::ScalarizeVecOp_VSELECT(SDNode *N) {
 555   SDValue ScalarCond = GetScalarizedVector(N->getOperand(0));
 556   EVT VT = N->getValueType(0);
 557
 558   return DAG.getNode(ISD::SELECT, SDLoc(N), VT, ScalarCond, N->getOperand(1),
 559                      N->getOperand(2));
 560 }
 561
 562 /// If the operand is a vector that needs to be scalarized then the
 563 /// result must be v1i1, so just convert to a scalar SETCC and wrap
 564 /// with a scalar_to_vector since the res type is legal if we got here
 565 SDValue DAGTypeLegalizer::ScalarizeVecOp_VSETCC(SDNode *N) {
 566   assert(N->getValueType(0).isVector() &&
 567          N->getOperand(0).getValueType().isVector() &&
 568          "Operand types must be vectors");
 569   assert(N->getValueType(0) == MVT::v1i1 && "Expected v1i1 type");
 570
 571   EVT VT = N->getValueType(0);
 572   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 573   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 574
 575   EVT OpVT = N->getOperand(0).getValueType();
 576   EVT NVT = VT.getVectorElementType();
 577   SDLoc DL(N);
 578   // Turn it into a scalar SETCC.
 579   SDValue Res = DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS,
 580       N->getOperand(2));
 581
 582   // Vectors may have a different boolean contents to scalars.  Promote the
 583   // value appropriately.
 584   ISD::NodeType ExtendCode =
 585       TargetLowering::getExtendForContent(TLI.getBooleanContents(OpVT));
 586
 587   Res = DAG.getNode(ExtendCode, DL, NVT, Res);
 588
 589   return DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VT, Res);
 590 }
 591
 592 /// If the value to store is a vector that needs to be scalarized, it must be
 593 /// <1 x ty>. Just store the element.
 594 SDValue DAGTypeLegalizer::ScalarizeVecOp_STORE(StoreSDNode *N, unsigned OpNo){
 595   assert(N->isUnindexed() && "Indexed store of one-element vector?");
 596   assert(OpNo == 1 && "Do not know how to scalarize this operand!");
 597   SDLoc dl(N);
 598
 599   if (N->isTruncatingStore())
 600     return DAG.getTruncStore(
 601         N->getChain(), dl, GetScalarizedVector(N->getOperand(1)),
 602         N->getBasePtr(), N->getPointerInfo(),
 603         N->getMemoryVT().getVectorElementType(), N->getAlignment(),
 604         N->getMemOperand()->getFlags(), N->getAAInfo());
 605
 606   return DAG.getStore(N->getChain(), dl, GetScalarizedVector(N->getOperand(1)),
 607                       N->getBasePtr(), N->getPointerInfo(),
 608                       N->getOriginalAlignment(), N->getMemOperand()->getFlags(),
 609                       N->getAAInfo());
 610 }
 611
 612 /// If the value to round is a vector that needs to be scalarized, it must be
 613 /// <1 x ty>. Convert the element instead.
 614 SDValue DAGTypeLegalizer::ScalarizeVecOp_FP_ROUND(SDNode *N, unsigned OpNo) {
 615   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 616   SDValue Res = DAG.getNode(ISD::FP_ROUND, SDLoc(N),
 617                             N->getValueType(0).getVectorElementType(), Elt,
 618                             N->getOperand(1));
 619   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N), N->getValueType(0), Res);
 620 }
 621
 622 //===----------------------------------------------------------------------===//
 623 //  Result Vector Splitting
 624 //===----------------------------------------------------------------------===//
 625
 626 /// This method is called when the specified result of the specified node is
 627 /// found to need vector splitting. At this point, the node may also have
 628 /// invalid operands or may have other results that need legalization, we just
 629 /// know that (at least) one result needs vector splitting.
 630 void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) {
 631   DEBUG(dbgs() << "Split node result: ";
 632         N->dump(&DAG);
 633         dbgs() << "\n");
 634   SDValue Lo, Hi;
 635
 636   // See if the target wants to custom expand this node.
 637   if (CustomLowerNode(N, N->getValueType(ResNo), true))
 638     return;
 639
 640   switch (N->getOpcode()) {
 641   default:
 642 #ifndef NDEBUG
 643     dbgs() << "SplitVectorResult #" << ResNo << ": ";
 644     N->dump(&DAG);
 645     dbgs() << "\n";
 646 #endif
 647     report_fatal_error("Do not know how to split the result of this "
 648                        "operator!\n");
 649
 650   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, ResNo, Lo, Hi); break;
 651   case ISD::VSELECT:
 652   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
 653   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
 654   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
 655   case ISD::BITCAST:           SplitVecRes_BITCAST(N, Lo, Hi); break;
 656   case ISD::BUILD_VECTOR:      SplitVecRes_BUILD_VECTOR(N, Lo, Hi); break;
 657   case ISD::CONCAT_VECTORS:    SplitVecRes_CONCAT_VECTORS(N, Lo, Hi); break;
 658   case ISD::EXTRACT_SUBVECTOR: SplitVecRes_EXTRACT_SUBVECTOR(N, Lo, Hi); break;
 659   case ISD::INSERT_SUBVECTOR:  SplitVecRes_INSERT_SUBVECTOR(N, Lo, Hi); break;
 660   case ISD::FP_ROUND_INREG:    SplitVecRes_InregOp(N, Lo, Hi); break;
 661   case ISD::FPOWI:             SplitVecRes_FPOWI(N, Lo, Hi); break;
 662   case ISD::FCOPYSIGN:         SplitVecRes_FCOPYSIGN(N, Lo, Hi); break;
 663   case ISD::INSERT_VECTOR_ELT: SplitVecRes_INSERT_VECTOR_ELT(N, Lo, Hi); break;
 664   case ISD::SCALAR_TO_VECTOR:  SplitVecRes_SCALAR_TO_VECTOR(N, Lo, Hi); break;
 665   case ISD::SIGN_EXTEND_INREG: SplitVecRes_InregOp(N, Lo, Hi); break;
 666   case ISD::LOAD:
 667     SplitVecRes_LOAD(cast<LoadSDNode>(N), Lo, Hi);
 668     break;
 669   case ISD::MLOAD:
 670     SplitVecRes_MLOAD(cast<MaskedLoadSDNode>(N), Lo, Hi);
 671     break;
 672   case ISD::MGATHER:
 673     SplitVecRes_MGATHER(cast<MaskedGatherSDNode>(N), Lo, Hi);
 674     break;
 675   case ISD::SETCC:
 676     SplitVecRes_SETCC(N, Lo, Hi);
 677     break;
 678   case ISD::VECTOR_SHUFFLE:
 679     SplitVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N), Lo, Hi);
 680     break;
 681
 682   case ISD::ANY_EXTEND_VECTOR_INREG:
 683   case ISD::SIGN_EXTEND_VECTOR_INREG:
 684   case ISD::ZERO_EXTEND_VECTOR_INREG:
 685     SplitVecRes_ExtVecInRegOp(N, Lo, Hi);
 686     break;
 687
 688   case ISD::BITREVERSE:
 689   case ISD::BSWAP:
 690   case ISD::CTLZ:
 691   case ISD::CTTZ:
 692   case ISD::CTLZ_ZERO_UNDEF:
 693   case ISD::CTTZ_ZERO_UNDEF:
 694   case ISD::CTPOP:
 695   case ISD::FABS:
 696   case ISD::FCEIL:
 697   case ISD::FCOS:
 698   case ISD::FEXP:
 699   case ISD::FEXP2:
 700   case ISD::FFLOOR:
 701   case ISD::FLOG:
 702   case ISD::FLOG10:
 703   case ISD::FLOG2:
 704   case ISD::FNEARBYINT:
 705   case ISD::FNEG:
 706   case ISD::FP_EXTEND:
 707   case ISD::FP_ROUND:
 708   case ISD::FP_TO_SINT:
 709   case ISD::FP_TO_UINT:
 710   case ISD::FRINT:
 711   case ISD::FROUND:
 712   case ISD::FSIN:
 713   case ISD::FSQRT:
 714   case ISD::FTRUNC:
 715   case ISD::SINT_TO_FP:
 716   case ISD::TRUNCATE:
 717   case ISD::UINT_TO_FP:
 718   case ISD::FCANONICALIZE:
 719     SplitVecRes_UnaryOp(N, Lo, Hi);
 720     break;
 721
 722   case ISD::ANY_EXTEND:
 723   case ISD::SIGN_EXTEND:
 724   case ISD::ZERO_EXTEND:
 725     SplitVecRes_ExtendOp(N, Lo, Hi);
 726     break;
 727
 728   case ISD::ADD:
 729   case ISD::SUB:
 730   case ISD::MUL:
 731   case ISD::MULHS:
 732   case ISD::MULHU:
 733   case ISD::FADD:
 734   case ISD::FSUB:
 735   case ISD::FMUL:
 736   case ISD::FMINNUM:
 737   case ISD::FMAXNUM:
 738   case ISD::FMINNAN:
 739   case ISD::FMAXNAN:
 740   case ISD::SDIV:
 741   case ISD::UDIV:
 742   case ISD::FDIV:
 743   case ISD::FPOW:
 744   case ISD::AND:
 745   case ISD::OR:
 746   case ISD::XOR:
 747   case ISD::SHL:
 748   case ISD::SRA:
 749   case ISD::SRL:
 750   case ISD::UREM:
 751   case ISD::SREM:
 752   case ISD::FREM:
 753   case ISD::SMIN:
 754   case ISD::SMAX:
 755   case ISD::UMIN:
 756   case ISD::UMAX:
 757     SplitVecRes_BinOp(N, Lo, Hi);
 758     break;
 759   case ISD::FMA:
 760     SplitVecRes_TernaryOp(N, Lo, Hi);
 761     break;
 762   }
 763
 764   // If Lo/Hi is null, the sub-method took care of registering results etc.
 765   if (Lo.getNode())
 766     SetSplitVector(SDValue(N, ResNo), Lo, Hi);
 767 }
 768
 769 void DAGTypeLegalizer::SplitVecRes_BinOp(SDNode *N, SDValue &Lo,
 770                                          SDValue &Hi) {
 771   SDValue LHSLo, LHSHi;
 772   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 773   SDValue RHSLo, RHSHi;
 774   GetSplitVector(N->getOperand(1), RHSLo, RHSHi);
 775   SDLoc dl(N);
 776
 777   const SDNodeFlags Flags = N->getFlags();
 778   unsigned Opcode = N->getOpcode();
 779   Lo = DAG.getNode(Opcode, dl, LHSLo.getValueType(), LHSLo, RHSLo, Flags);
 780   Hi = DAG.getNode(Opcode, dl, LHSHi.getValueType(), LHSHi, RHSHi, Flags);
 781 }
 782
 783 void DAGTypeLegalizer::SplitVecRes_TernaryOp(SDNode *N, SDValue &Lo,
 784                                              SDValue &Hi) {
 785   SDValue Op0Lo, Op0Hi;
 786   GetSplitVector(N->getOperand(0), Op0Lo, Op0Hi);
 787   SDValue Op1Lo, Op1Hi;
 788   GetSplitVector(N->getOperand(1), Op1Lo, Op1Hi);
 789   SDValue Op2Lo, Op2Hi;
 790   GetSplitVector(N->getOperand(2), Op2Lo, Op2Hi);
 791   SDLoc dl(N);
 792
 793   Lo = DAG.getNode(N->getOpcode(), dl, Op0Lo.getValueType(),
 794                    Op0Lo, Op1Lo, Op2Lo);
 795   Hi = DAG.getNode(N->getOpcode(), dl, Op0Hi.getValueType(),
 796                    Op0Hi, Op1Hi, Op2Hi);
 797 }
 798
 799 void DAGTypeLegalizer::SplitVecRes_BITCAST(SDNode *N, SDValue &Lo,
 800                                            SDValue &Hi) {
 801   // We know the result is a vector.  The input may be either a vector or a
 802   // scalar value.
 803   EVT LoVT, HiVT;
 804   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
 805   SDLoc dl(N);
 806
 807   SDValue InOp = N->getOperand(0);
 808   EVT InVT = InOp.getValueType();
 809
 810   // Handle some special cases efficiently.
 811   switch (getTypeAction(InVT)) {
 812   case TargetLowering::TypeLegal:
 813   case TargetLowering::TypePromoteInteger:
 814   case TargetLowering::TypePromoteFloat:
 815   case TargetLowering::TypeSoftenFloat:
 816   case TargetLowering::TypeScalarizeVector:
 817   case TargetLowering::TypeWidenVector:
 818     break;
 819   case TargetLowering::TypeExpandInteger:
 820   case TargetLowering::TypeExpandFloat:
 821     // A scalar to vector conversion, where the scalar needs expansion.
 822     // If the vector is being split in two then we can just convert the
 823     // expanded pieces.
 824     if (LoVT == HiVT) {
 825       GetExpandedOp(InOp, Lo, Hi);
 826       if (DAG.getDataLayout().isBigEndian())
 827         std::swap(Lo, Hi);
 828       Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 829       Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 830       return;
 831     }
 832     break;
 833   case TargetLowering::TypeSplitVector:
 834     // If the input is a vector that needs to be split, convert each split
 835     // piece of the input now.
 836     GetSplitVector(InOp, Lo, Hi);
 837     Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 838     Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 839     return;
 840   }
 841
 842   // In the general case, convert the input to an integer and split it by hand.
 843   EVT LoIntVT = EVT::getIntegerVT(*DAG.getContext(), LoVT.getSizeInBits());
 844   EVT HiIntVT = EVT::getIntegerVT(*DAG.getContext(), HiVT.getSizeInBits());
 845   if (DAG.getDataLayout().isBigEndian())
 846     std::swap(LoIntVT, HiIntVT);
 847
 848   SplitInteger(BitConvertToInteger(InOp), LoIntVT, HiIntVT, Lo, Hi);
 849
 850   if (DAG.getDataLayout().isBigEndian())
 851     std::swap(Lo, Hi);
 852   Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 853   Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 854 }
 855
 856 void DAGTypeLegalizer::SplitVecRes_BUILD_VECTOR(SDNode *N, SDValue &Lo,
 857                                                 SDValue &Hi) {
 858   EVT LoVT, HiVT;
 859   SDLoc dl(N);
 860   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
 861   unsigned LoNumElts = LoVT.getVectorNumElements();
 862   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+LoNumElts);
 863   Lo = DAG.getBuildVector(LoVT, dl, LoOps);
 864
 865   SmallVector<SDValue, 8> HiOps(N->op_begin()+LoNumElts, N->op_end());
 866   Hi = DAG.getBuildVector(HiVT, dl, HiOps);
 867 }
 868
 869 void DAGTypeLegalizer::SplitVecRes_CONCAT_VECTORS(SDNode *N, SDValue &Lo,
 870                                                   SDValue &Hi) {
 871   assert(!(N->getNumOperands() & 1) && "Unsupported CONCAT_VECTORS");
 872   SDLoc dl(N);
 873   unsigned NumSubvectors = N->getNumOperands() / 2;
 874   if (NumSubvectors == 1) {
 875     Lo = N->getOperand(0);
 876     Hi = N->getOperand(1);
 877     return;
 878   }
 879
 880   EVT LoVT, HiVT;
 881   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
 882
 883   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+NumSubvectors);
 884   Lo = DAG.getNode(ISD::CONCAT_VECTORS, dl, LoVT, LoOps);
 885
 886   SmallVector<SDValue, 8> HiOps(N->op_begin()+NumSubvectors, N->op_end());
 887   Hi = DAG.getNode(ISD::CONCAT_VECTORS, dl, HiVT, HiOps);
 888 }
 889
 890 void DAGTypeLegalizer::SplitVecRes_EXTRACT_SUBVECTOR(SDNode *N, SDValue &Lo,
 891                                                      SDValue &Hi) {
 892   SDValue Vec = N->getOperand(0);
 893   SDValue Idx = N->getOperand(1);
 894   SDLoc dl(N);
 895
 896   EVT LoVT, HiVT;
 897   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
 898
 899   Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, LoVT, Vec, Idx);
 900   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
 901   Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, HiVT, Vec,
 902                    DAG.getConstant(IdxVal + LoVT.getVectorNumElements(), dl,
 903                                    TLI.getVectorIdxTy(DAG.getDataLayout())));
 904 }
 905
 906 void DAGTypeLegalizer::SplitVecRes_INSERT_SUBVECTOR(SDNode *N, SDValue &Lo,
 907                                                     SDValue &Hi) {
 908   SDValue Vec = N->getOperand(0);
 909   SDValue SubVec = N->getOperand(1);
 910   SDValue Idx = N->getOperand(2);
 911   SDLoc dl(N);
 912   GetSplitVector(Vec, Lo, Hi);
 913
 914   EVT VecVT = Vec.getValueType();
 915   unsigned VecElems = VecVT.getVectorNumElements();
 916   unsigned SubElems = SubVec.getValueType().getVectorNumElements();
 917
 918   // If we know the index is 0, and we know the subvector doesn't cross the
 919   // boundary between the halves, we can avoid spilling the vector, and insert
 920   // into the lower half of the split vector directly.
 921   // TODO: The IdxVal == 0 constraint is artificial, we could do this whenever
 922   // the index is constant and there is no boundary crossing. But those cases
 923   // don't seem to get hit in practice.
 924   if (ConstantSDNode *ConstIdx = dyn_cast<ConstantSDNode>(Idx)) {
 925     unsigned IdxVal = ConstIdx->getZExtValue();
 926     if ((IdxVal == 0) && (IdxVal + SubElems <= VecElems / 2)) {
 927       EVT LoVT, HiVT;
 928       std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
 929       Lo = DAG.getNode(ISD::INSERT_SUBVECTOR, dl, LoVT, Lo, SubVec, Idx);
 930       return;
 931     }
 932   }
 933
 934   // Spill the vector to the stack.
 935   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
 936   SDValue Store =
 937       DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, MachinePointerInfo());
 938
 939   // Store the new subvector into the specified index.
 940   SDValue SubVecPtr = TLI.getVectorElementPointer(DAG, StackPtr, VecVT, Idx);
 941   Type *VecType = VecVT.getTypeForEVT(*DAG.getContext());
 942   unsigned Alignment = DAG.getDataLayout().getPrefTypeAlignment(VecType);
 943   Store = DAG.getStore(Store, dl, SubVec, SubVecPtr, MachinePointerInfo());
 944
 945   // Load the Lo part from the stack slot.
 946   Lo =
 947       DAG.getLoad(Lo.getValueType(), dl, Store, StackPtr, MachinePointerInfo());
 948
 949   // Increment the pointer to the other part.
 950   unsigned IncrementSize = Lo.getValueSizeInBits() / 8;
 951   StackPtr =
 952       DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 953                   DAG.getConstant(IncrementSize, dl, StackPtr.getValueType()));
 954
 955   // Load the Hi part from the stack slot.
 956   Hi = DAG.getLoad(Hi.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
 957                    MinAlign(Alignment, IncrementSize));
 958 }
 959
 960 void DAGTypeLegalizer::SplitVecRes_FPOWI(SDNode *N, SDValue &Lo,
 961                                          SDValue &Hi) {
 962   SDLoc dl(N);
 963   GetSplitVector(N->getOperand(0), Lo, Hi);
 964   Lo = DAG.getNode(ISD::FPOWI, dl, Lo.getValueType(), Lo, N->getOperand(1));
 965   Hi = DAG.getNode(ISD::FPOWI, dl, Hi.getValueType(), Hi, N->getOperand(1));
 966 }
 967
 968 void DAGTypeLegalizer::SplitVecRes_FCOPYSIGN(SDNode *N, SDValue &Lo,
 969                                              SDValue &Hi) {
 970   SDValue LHSLo, LHSHi;
 971   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 972   SDLoc DL(N);
 973
 974   SDValue RHSLo, RHSHi;
 975   SDValue RHS = N->getOperand(1);
 976   EVT RHSVT = RHS.getValueType();
 977   if (getTypeAction(RHSVT) == TargetLowering::TypeSplitVector)
 978     GetSplitVector(RHS, RHSLo, RHSHi);
 979   else
 980     std::tie(RHSLo, RHSHi) = DAG.SplitVector(RHS, SDLoc(RHS));
 981
 982
 983   Lo = DAG.getNode(ISD::FCOPYSIGN, DL, LHSLo.getValueType(), LHSLo, RHSLo);
 984   Hi = DAG.getNode(ISD::FCOPYSIGN, DL, LHSHi.getValueType(), LHSHi, RHSHi);
 985 }
 986
 987 void DAGTypeLegalizer::SplitVecRes_InregOp(SDNode *N, SDValue &Lo,
 988                                            SDValue &Hi) {
 989   SDValue LHSLo, LHSHi;
 990   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 991   SDLoc dl(N);
 992
 993   EVT LoVT, HiVT;
 994   std::tie(LoVT, HiVT) =
 995     DAG.GetSplitDestVTs(cast<VTSDNode>(N->getOperand(1))->getVT());
 996
 997   Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo,
 998                    DAG.getValueType(LoVT));
 999   Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi,
1000                    DAG.getValueType(HiVT));
1001 }
1002
1003 void DAGTypeLegalizer::SplitVecRes_ExtVecInRegOp(SDNode *N, SDValue &Lo,
1004                                                  SDValue &Hi) {
1005   unsigned Opcode = N->getOpcode();
1006   SDValue N0 = N->getOperand(0);
1007
1008   SDLoc dl(N);
1009   SDValue InLo, InHi;
1010
1011   if (getTypeAction(N0.getValueType()) == TargetLowering::TypeSplitVector)
1012     GetSplitVector(N0, InLo, InHi);
1013   else
1014     std::tie(InLo, InHi) = DAG.SplitVectorOperand(N, 0);
1015
1016   EVT InLoVT = InLo.getValueType();
1017   unsigned InNumElements = InLoVT.getVectorNumElements();
1018
1019   EVT OutLoVT, OutHiVT;
1020   std::tie(OutLoVT, OutHiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1021   unsigned OutNumElements = OutLoVT.getVectorNumElements();
1022   assert((2 * OutNumElements) <= InNumElements &&
1023          "Illegal extend vector in reg split");
1024
1025   // *_EXTEND_VECTOR_INREG instructions extend the lowest elements of the
1026   // input vector (i.e. we only use InLo):
1027   // OutLo will extend the first OutNumElements from InLo.
1028   // OutHi will extend the next OutNumElements from InLo.
1029
1030   // Shuffle the elements from InLo for OutHi into the bottom elements to
1031   // create a 'fake' InHi.
1032   SmallVector<int, 8> SplitHi(InNumElements, -1);
1033   for (unsigned i = 0; i != OutNumElements; ++i)
1034     SplitHi[i] = i + OutNumElements;
1035   InHi = DAG.getVectorShuffle(InLoVT, dl, InLo, DAG.getUNDEF(InLoVT), SplitHi);
1036
1037   Lo = DAG.getNode(Opcode, dl, OutLoVT, InLo);
1038   Hi = DAG.getNode(Opcode, dl, OutHiVT, InHi);
1039 }
1040
1041 void DAGTypeLegalizer::SplitVecRes_INSERT_VECTOR_ELT(SDNode *N, SDValue &Lo,
1042                                                      SDValue &Hi) {
1043   SDValue Vec = N->getOperand(0);
1044   SDValue Elt = N->getOperand(1);
1045   SDValue Idx = N->getOperand(2);
1046   SDLoc dl(N);
1047   GetSplitVector(Vec, Lo, Hi);
1048
1049   if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
1050     unsigned IdxVal = CIdx->getZExtValue();
1051     unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
1052     if (IdxVal < LoNumElts)
1053       Lo = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl,
1054                        Lo.getValueType(), Lo, Elt, Idx);
1055     else
1056       Hi =
1057           DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, Hi.getValueType(), Hi, Elt,
1058                       DAG.getConstant(IdxVal - LoNumElts, dl,
1059                                       TLI.getVectorIdxTy(DAG.getDataLayout())));
1060     return;
1061   }
1062
1063   // See if the target wants to custom expand this node.
1064   if (CustomLowerNode(N, N->getValueType(0), true))
1065     return;
1066
1067   // Make the vector elements byte-addressable if they aren't already.
1068   EVT VecVT = Vec.getValueType();
1069   EVT EltVT = VecVT.getVectorElementType();
1070   if (VecVT.getScalarSizeInBits() < 8) {
1071     EltVT = MVT::i8;
1072     VecVT = EVT::getVectorVT(*DAG.getContext(), EltVT,
1073                              VecVT.getVectorNumElements());
1074     Vec = DAG.getNode(ISD::ANY_EXTEND, dl, VecVT, Vec);
1075     // Extend the element type to match if needed.
1076     if (EltVT.bitsGT(Elt.getValueType()))
1077       Elt = DAG.getNode(ISD::ANY_EXTEND, dl, EltVT, Elt);
1078   }
1079
1080   // Spill the vector to the stack.
1081   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
1082   auto &MF = DAG.getMachineFunction();
1083   auto FrameIndex = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
1084   auto PtrInfo = MachinePointerInfo::getFixedStack(MF, FrameIndex);
1085   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, PtrInfo);
1086
1087   // Store the new element.  This may be larger than the vector element type,
1088   // so use a truncating store.
1089   SDValue EltPtr = TLI.getVectorElementPointer(DAG, StackPtr, VecVT, Idx);
1090   Type *VecType = VecVT.getTypeForEVT(*DAG.getContext());
1091   unsigned Alignment = DAG.getDataLayout().getPrefTypeAlignment(VecType);
1092   Store = DAG.getTruncStore(Store, dl, Elt, EltPtr,
1093                             MachinePointerInfo::getUnknownStack(MF), EltVT);
1094
1095   EVT LoVT, HiVT;
1096   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(VecVT);
1097
1098   // Load the Lo part from the stack slot.
1099   Lo = DAG.getLoad(LoVT, dl, Store, StackPtr, PtrInfo);
1100
1101   // Increment the pointer to the other part.
1102   unsigned IncrementSize = LoVT.getSizeInBits() / 8;
1103   StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
1104                          DAG.getConstant(IncrementSize, dl,
1105                                          StackPtr.getValueType()));
1106
1107   // Load the Hi part from the stack slot.
1108   Hi = DAG.getLoad(HiVT, dl, Store, StackPtr,
1109                    PtrInfo.getWithOffset(IncrementSize),
1110                    MinAlign(Alignment, IncrementSize));
1111
1112   // If we adjusted the original type, we need to truncate the results.
1113   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1114   if (LoVT != Lo.getValueType())
1115     Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Lo);
1116   if (HiVT != Hi.getValueType())
1117     Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi);
1118 }
1119
1120 void DAGTypeLegalizer::SplitVecRes_SCALAR_TO_VECTOR(SDNode *N, SDValue &Lo,
1121                                                     SDValue &Hi) {
1122   EVT LoVT, HiVT;
1123   SDLoc dl(N);
1124   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1125   Lo = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, LoVT, N->getOperand(0));
1126   Hi = DAG.getUNDEF(HiVT);
1127 }
1128
1129 void DAGTypeLegalizer::SplitVecRes_LOAD(LoadSDNode *LD, SDValue &Lo,
1130                                         SDValue &Hi) {
1131   assert(ISD::isUNINDEXEDLoad(LD) && "Indexed load during type legalization!");
1132   EVT LoVT, HiVT;
1133   SDLoc dl(LD);
1134   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(LD->getValueType(0));
1135
1136   ISD::LoadExtType ExtType = LD->getExtensionType();
1137   SDValue Ch = LD->getChain();
1138   SDValue Ptr = LD->getBasePtr();
1139   SDValue Offset = DAG.getUNDEF(Ptr.getValueType());
1140   EVT MemoryVT = LD->getMemoryVT();
1141   unsigned Alignment = LD->getOriginalAlignment();
1142   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
1143   AAMDNodes AAInfo = LD->getAAInfo();
1144
1145   EVT LoMemVT, HiMemVT;
1146   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1147
1148   Lo = DAG.getLoad(ISD::UNINDEXED, ExtType, LoVT, dl, Ch, Ptr, Offset,
1149                    LD->getPointerInfo(), LoMemVT, Alignment, MMOFlags, AAInfo);
1150
1151   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
1152   Ptr = DAG.getObjectPtrOffset(dl, Ptr, IncrementSize);
1153   Hi = DAG.getLoad(ISD::UNINDEXED, ExtType, HiVT, dl, Ch, Ptr, Offset,
1154                    LD->getPointerInfo().getWithOffset(IncrementSize), HiMemVT,
1155                    Alignment, MMOFlags, AAInfo);
1156
1157   // Build a factor node to remember that this load is independent of the
1158   // other one.
1159   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1160                    Hi.getValue(1));
1161
1162   // Legalize the chain result - switch anything that used the old chain to
1163   // use the new one.
1164   ReplaceValueWith(SDValue(LD, 1), Ch);
1165 }
1166
1167 void DAGTypeLegalizer::SplitVecRes_MLOAD(MaskedLoadSDNode *MLD,
1168                                          SDValue &Lo, SDValue &Hi) {
1169   EVT LoVT, HiVT;
1170   SDLoc dl(MLD);
1171   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(MLD->getValueType(0));
1172
1173   SDValue Ch = MLD->getChain();
1174   SDValue Ptr = MLD->getBasePtr();
1175   SDValue Mask = MLD->getMask();
1176   SDValue Src0 = MLD->getSrc0();
1177   unsigned Alignment = MLD->getOriginalAlignment();
1178   ISD::LoadExtType ExtType = MLD->getExtensionType();
1179
1180   // if Alignment is equal to the vector size,
1181   // take the half of it for the second part
1182   unsigned SecondHalfAlignment =
1183     (Alignment == MLD->getValueType(0).getSizeInBits()/8) ?
1184      Alignment/2 : Alignment;
1185
1186   // Split Mask operand
1187   SDValue MaskLo, MaskHi;
1188   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1189     GetSplitVector(Mask, MaskLo, MaskHi);
1190   else
1191     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, dl);
1192
1193   EVT MemoryVT = MLD->getMemoryVT();
1194   EVT LoMemVT, HiMemVT;
1195   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1196
1197   SDValue Src0Lo, Src0Hi;
1198   if (getTypeAction(Src0.getValueType()) == TargetLowering::TypeSplitVector)
1199     GetSplitVector(Src0, Src0Lo, Src0Hi);
1200   else
1201     std::tie(Src0Lo, Src0Hi) = DAG.SplitVector(Src0, dl);
1202
1203   MachineMemOperand *MMO = DAG.getMachineFunction().
1204     getMachineMemOperand(MLD->getPointerInfo(),
1205                          MachineMemOperand::MOLoad,  LoMemVT.getStoreSize(),
1206                          Alignment, MLD->getAAInfo(), MLD->getRanges());
1207
1208   Lo = DAG.getMaskedLoad(LoVT, dl, Ch, Ptr, MaskLo, Src0Lo, LoMemVT, MMO,
1209                          ExtType, MLD->isExpandingLoad());
1210
1211   Ptr = TLI.IncrementMemoryAddress(Ptr, MaskLo, dl, LoMemVT, DAG,
1212                                    MLD->isExpandingLoad());
1213   unsigned HiOffset = LoMemVT.getStoreSize();
1214
1215   MMO = DAG.getMachineFunction().getMachineMemOperand(
1216       MLD->getPointerInfo().getWithOffset(HiOffset), MachineMemOperand::MOLoad,
1217       HiMemVT.getStoreSize(), SecondHalfAlignment, MLD->getAAInfo(),
1218       MLD->getRanges());
1219
1220   Hi = DAG.getMaskedLoad(HiVT, dl, Ch, Ptr, MaskHi, Src0Hi, HiMemVT, MMO,
1221                          ExtType, MLD->isExpandingLoad());
1222
1223   // Build a factor node to remember that this load is independent of the
1224   // other one.
1225   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1226                    Hi.getValue(1));
1227
1228   // Legalize the chain result - switch anything that used the old chain to
1229   // use the new one.
1230   ReplaceValueWith(SDValue(MLD, 1), Ch);
1231
1232 }
1233
1234 void DAGTypeLegalizer::SplitVecRes_MGATHER(MaskedGatherSDNode *MGT,
1235                                          SDValue &Lo, SDValue &Hi) {
1236   EVT LoVT, HiVT;
1237   SDLoc dl(MGT);
1238   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(MGT->getValueType(0));
1239
1240   SDValue Ch = MGT->getChain();
1241   SDValue Ptr = MGT->getBasePtr();
1242   SDValue Mask = MGT->getMask();
1243   SDValue Src0 = MGT->getValue();
1244   SDValue Index = MGT->getIndex();
1245   SDValue Scale = MGT->getScale();
1246   unsigned Alignment = MGT->getOriginalAlignment();
1247
1248   // Split Mask operand
1249   SDValue MaskLo, MaskHi;
1250   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1251     GetSplitVector(Mask, MaskLo, MaskHi);
1252   else
1253     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, dl);
1254
1255   EVT MemoryVT = MGT->getMemoryVT();
1256   EVT LoMemVT, HiMemVT;
1257   // Split MemoryVT
1258   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1259
1260   SDValue Src0Lo, Src0Hi;
1261   if (getTypeAction(Src0.getValueType()) == TargetLowering::TypeSplitVector)
1262     GetSplitVector(Src0, Src0Lo, Src0Hi);
1263   else
1264     std::tie(Src0Lo, Src0Hi) = DAG.SplitVector(Src0, dl);
1265
1266   SDValue IndexHi, IndexLo;
1267   if (getTypeAction(Index.getValueType()) == TargetLowering::TypeSplitVector)
1268     GetSplitVector(Index, IndexLo, IndexHi);
1269   else
1270     std::tie(IndexLo, IndexHi) = DAG.SplitVector(Index, dl);
1271
1272   MachineMemOperand *MMO = DAG.getMachineFunction().
1273     getMachineMemOperand(MGT->getPointerInfo(),
1274                          MachineMemOperand::MOLoad,  LoMemVT.getStoreSize(),
1275                          Alignment, MGT->getAAInfo(), MGT->getRanges());
1276
1277   SDValue OpsLo[] = {Ch, Src0Lo, MaskLo, Ptr, IndexLo, Scale};
1278   Lo = DAG.getMaskedGather(DAG.getVTList(LoVT, MVT::Other), LoVT, dl, OpsLo,
1279                            MMO);
1280
1281   SDValue OpsHi[] = {Ch, Src0Hi, MaskHi, Ptr, IndexHi, Scale};
1282   Hi = DAG.getMaskedGather(DAG.getVTList(HiVT, MVT::Other), HiVT, dl, OpsHi,
1283                            MMO);
1284
1285   // Build a factor node to remember that this load is independent of the
1286   // other one.
1287   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1288                    Hi.getValue(1));
1289
1290   // Legalize the chain result - switch anything that used the old chain to
1291   // use the new one.
1292   ReplaceValueWith(SDValue(MGT, 1), Ch);
1293 }
1294
1295
1296 void DAGTypeLegalizer::SplitVecRes_SETCC(SDNode *N, SDValue &Lo, SDValue &Hi) {
1297   assert(N->getValueType(0).isVector() &&
1298          N->getOperand(0).getValueType().isVector() &&
1299          "Operand types must be vectors");
1300
1301   EVT LoVT, HiVT;
1302   SDLoc DL(N);
1303   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1304
1305   // If the input also splits, handle it directly. Otherwise split it by hand.
1306   SDValue LL, LH, RL, RH;
1307   if (getTypeAction(N->getOperand(0).getValueType()) ==
1308       TargetLowering::TypeSplitVector)
1309     GetSplitVector(N->getOperand(0), LL, LH);
1310   else
1311     std::tie(LL, LH) = DAG.SplitVectorOperand(N, 0);
1312
1313   if (getTypeAction(N->getOperand(1).getValueType()) ==
1314       TargetLowering::TypeSplitVector)
1315     GetSplitVector(N->getOperand(1), RL, RH);
1316   else
1317     std::tie(RL, RH) = DAG.SplitVectorOperand(N, 1);
1318
1319   Lo = DAG.getNode(N->getOpcode(), DL, LoVT, LL, RL, N->getOperand(2));
1320   Hi = DAG.getNode(N->getOpcode(), DL, HiVT, LH, RH, N->getOperand(2));
1321 }
1322
1323 void DAGTypeLegalizer::SplitVecRes_UnaryOp(SDNode *N, SDValue &Lo,
1324                                            SDValue &Hi) {
1325   // Get the dest types - they may not match the input types, e.g. int_to_fp.
1326   EVT LoVT, HiVT;
1327   SDLoc dl(N);
1328   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1329
1330   // If the input also splits, handle it directly for a compile time speedup.
1331   // Otherwise split it by hand.
1332   EVT InVT = N->getOperand(0).getValueType();
1333   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector)
1334     GetSplitVector(N->getOperand(0), Lo, Hi);
1335   else
1336     std::tie(Lo, Hi) = DAG.SplitVectorOperand(N, 0);
1337
1338   if (N->getOpcode() == ISD::FP_ROUND) {
1339     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo, N->getOperand(1));
1340     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi, N->getOperand(1));
1341   } else {
1342     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
1343     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
1344   }
1345 }
1346
1347 void DAGTypeLegalizer::SplitVecRes_ExtendOp(SDNode *N, SDValue &Lo,
1348                                             SDValue &Hi) {
1349   SDLoc dl(N);
1350   EVT SrcVT = N->getOperand(0).getValueType();
1351   EVT DestVT = N->getValueType(0);
1352   EVT LoVT, HiVT;
1353   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(DestVT);
1354
1355   // We can do better than a generic split operation if the extend is doing
1356   // more than just doubling the width of the elements and the following are
1357   // true:
1358   //   - The number of vector elements is even,
1359   //   - the source type is legal,
1360   //   - the type of a split source is illegal,
1361   //   - the type of an extended (by doubling element size) source is legal, and
1362   //   - the type of that extended source when split is legal.
1363   //
1364   // This won't necessarily completely legalize the operation, but it will
1365   // more effectively move in the right direction and prevent falling down
1366   // to scalarization in many cases due to the input vector being split too
1367   // far.
1368   unsigned NumElements = SrcVT.getVectorNumElements();
1369   if ((NumElements & 1) == 0 &&
1370       SrcVT.getSizeInBits() * 2 < DestVT.getSizeInBits()) {
1371     LLVMContext &Ctx = *DAG.getContext();
1372     EVT NewSrcVT = SrcVT.widenIntegerVectorElementType(Ctx);
1373     EVT SplitSrcVT = SrcVT.getHalfNumVectorElementsVT(Ctx);
1374
1375     EVT SplitLoVT, SplitHiVT;
1376     std::tie(SplitLoVT, SplitHiVT) = DAG.GetSplitDestVTs(NewSrcVT);
1377     if (TLI.isTypeLegal(SrcVT) && !TLI.isTypeLegal(SplitSrcVT) &&
1378         TLI.isTypeLegal(NewSrcVT) && TLI.isTypeLegal(SplitLoVT)) {
1379       DEBUG(dbgs() << "Split vector extend via incremental extend:";
1380             N->dump(&DAG); dbgs() << "\n");
1381       // Extend the source vector by one step.
1382       SDValue NewSrc =
1383           DAG.getNode(N->getOpcode(), dl, NewSrcVT, N->getOperand(0));
1384       // Get the low and high halves of the new, extended one step, vector.
1385       std::tie(Lo, Hi) = DAG.SplitVector(NewSrc, dl);
1386       // Extend those vector halves the rest of the way.
1387       Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
1388       Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
1389       return;
1390     }
1391   }
1392   // Fall back to the generic unary operator splitting otherwise.
1393   SplitVecRes_UnaryOp(N, Lo, Hi);
1394 }
1395
1396 void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N,
1397                                                   SDValue &Lo, SDValue &Hi) {
1398   // The low and high parts of the original input give four input vectors.
1399   SDValue Inputs[4];
1400   SDLoc dl(N);
1401   GetSplitVector(N->getOperand(0), Inputs[0], Inputs[1]);
1402   GetSplitVector(N->getOperand(1), Inputs[2], Inputs[3]);
1403   EVT NewVT = Inputs[0].getValueType();
1404   unsigned NewElts = NewVT.getVectorNumElements();
1405
1406   // If Lo or Hi uses elements from at most two of the four input vectors, then
1407   // express it as a vector shuffle of those two inputs.  Otherwise extract the
1408   // input elements by hand and construct the Lo/Hi output using a BUILD_VECTOR.
1409   SmallVector<int, 16> Ops;
1410   for (unsigned High = 0; High < 2; ++High) {
1411     SDValue &Output = High ? Hi : Lo;
1412
1413     // Build a shuffle mask for the output, discovering on the fly which
1414     // input vectors to use as shuffle operands (recorded in InputUsed).
1415     // If building a suitable shuffle vector proves too hard, then bail
1416     // out with useBuildVector set.
1417     unsigned InputUsed[2] = { -1U, -1U }; // Not yet discovered.
1418     unsigned FirstMaskIdx = High * NewElts;
1419     bool useBuildVector = false;
1420     for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
1421       // The mask element.  This indexes into the input.
1422       int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
1423
1424       // The input vector this mask element indexes into.
1425       unsigned Input = (unsigned)Idx / NewElts;
1426
1427       if (Input >= array_lengthof(Inputs)) {
1428         // The mask element does not index into any input vector.
1429         Ops.push_back(-1);
1430         continue;
1431       }
1432
1433       // Turn the index into an offset from the start of the input vector.
1434       Idx -= Input * NewElts;
1435
1436       // Find or create a shuffle vector operand to hold this input.
1437       unsigned OpNo;
1438       for (OpNo = 0; OpNo < array_lengthof(InputUsed); ++OpNo) {
1439         if (InputUsed[OpNo] == Input) {
1440           // This input vector is already an operand.
1441           break;
1442         } else if (InputUsed[OpNo] == -1U) {
1443           // Create a new operand for this input vector.
1444           InputUsed[OpNo] = Input;
1445           break;
1446         }
1447       }
1448
1449       if (OpNo >= array_lengthof(InputUsed)) {
1450         // More than two input vectors used!  Give up on trying to create a
1451         // shuffle vector.  Insert all elements into a BUILD_VECTOR instead.
1452         useBuildVector = true;
1453         break;
1454       }
1455
1456       // Add the mask index for the new shuffle vector.
1457       Ops.push_back(Idx + OpNo * NewElts);
1458     }
1459
1460     if (useBuildVector) {
1461       EVT EltVT = NewVT.getVectorElementType();
1462       SmallVector<SDValue, 16> SVOps;
1463
1464       // Extract the input elements by hand.
1465       for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
1466         // The mask element.  This indexes into the input.
1467         int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
1468
1469         // The input vector this mask element indexes into.
1470         unsigned Input = (unsigned)Idx / NewElts;
1471
1472         if (Input >= array_lengthof(Inputs)) {
1473           // The mask element is "undef" or indexes off the end of the input.
1474           SVOps.push_back(DAG.getUNDEF(EltVT));
1475           continue;
1476         }
1477
1478         // Turn the index into an offset from the start of the input vector.
1479         Idx -= Input * NewElts;
1480
1481         // Extract the vector element by hand.
1482         SVOps.push_back(DAG.getNode(
1483             ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Inputs[Input],
1484             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout()))));
1485       }
1486
1487       // Construct the Lo/Hi output using a BUILD_VECTOR.
1488       Output = DAG.getBuildVector(NewVT, dl, SVOps);
1489     } else if (InputUsed[0] == -1U) {
1490       // No input vectors were used!  The result is undefined.
1491       Output = DAG.getUNDEF(NewVT);
1492     } else {
1493       SDValue Op0 = Inputs[InputUsed[0]];
1494       // If only one input was used, use an undefined vector for the other.
1495       SDValue Op1 = InputUsed[1] == -1U ?
1496         DAG.getUNDEF(NewVT) : Inputs[InputUsed[1]];
1497       // At least one input vector was used.  Create a new shuffle vector.
1498       Output =  DAG.getVectorShuffle(NewVT, dl, Op0, Op1, Ops);
1499     }
1500
1501     Ops.clear();
1502   }
1503 }
1504
1505
1506 //===----------------------------------------------------------------------===//
1507 //  Operand Vector Splitting
1508 //===----------------------------------------------------------------------===//
1509
1510 /// This method is called when the specified operand of the specified node is
1511 /// found to need vector splitting. At this point, all of the result types of
1512 /// the node are known to be legal, but other operands of the node may need
1513 /// legalization as well as the specified one.
1514 bool DAGTypeLegalizer::SplitVectorOperand(SDNode *N, unsigned OpNo) {
1515   DEBUG(dbgs() << "Split node operand: ";
1516         N->dump(&DAG);
1517         dbgs() << "\n");
1518   SDValue Res = SDValue();
1519
1520   // See if the target wants to custom split this node.
1521   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
1522     return false;
1523
1524   if (!Res.getNode()) {
1525     switch (N->getOpcode()) {
1526     default:
1527 #ifndef NDEBUG
1528       dbgs() << "SplitVectorOperand Op #" << OpNo << ": ";
1529       N->dump(&DAG);
1530       dbgs() << "\n";
1531 #endif
1532       report_fatal_error("Do not know how to split this operator's "
1533                          "operand!\n");
1534
1535     case ISD::SETCC:             Res = SplitVecOp_VSETCC(N); break;
1536     case ISD::BITCAST:           Res = SplitVecOp_BITCAST(N); break;
1537     case ISD::EXTRACT_SUBVECTOR: Res = SplitVecOp_EXTRACT_SUBVECTOR(N); break;
1538     case ISD::EXTRACT_VECTOR_ELT:Res = SplitVecOp_EXTRACT_VECTOR_ELT(N); break;
1539     case ISD::CONCAT_VECTORS:    Res = SplitVecOp_CONCAT_VECTORS(N); break;
1540     case ISD::TRUNCATE:
1541       Res = SplitVecOp_TruncateHelper(N);
1542       break;
1543     case ISD::FP_ROUND:          Res = SplitVecOp_FP_ROUND(N); break;
1544     case ISD::FCOPYSIGN:         Res = SplitVecOp_FCOPYSIGN(N); break;
1545     case ISD::STORE:
1546       Res = SplitVecOp_STORE(cast<StoreSDNode>(N), OpNo);
1547       break;
1548     case ISD::MSTORE:
1549       Res = SplitVecOp_MSTORE(cast<MaskedStoreSDNode>(N), OpNo);
1550       break;
1551     case ISD::MSCATTER:
1552       Res = SplitVecOp_MSCATTER(cast<MaskedScatterSDNode>(N), OpNo);
1553       break;
1554     case ISD::MGATHER:
1555       Res = SplitVecOp_MGATHER(cast<MaskedGatherSDNode>(N), OpNo);
1556       break;
1557     case ISD::VSELECT:
1558       Res = SplitVecOp_VSELECT(N, OpNo);
1559       break;
1560     case ISD::FP_TO_SINT:
1561     case ISD::FP_TO_UINT:
1562       if (N->getValueType(0).bitsLT(N->getOperand(0).getValueType()))
1563         Res = SplitVecOp_TruncateHelper(N);
1564       else
1565         Res = SplitVecOp_UnaryOp(N);
1566       break;
1567     case ISD::SINT_TO_FP:
1568     case ISD::UINT_TO_FP:
1569       if (N->getValueType(0).bitsLT(N->getOperand(0).getValueType()))
1570         Res = SplitVecOp_TruncateHelper(N);
1571       else
1572         Res = SplitVecOp_UnaryOp(N);
1573       break;
1574     case ISD::CTTZ:
1575     case ISD::CTLZ:
1576     case ISD::CTPOP:
1577     case ISD::FP_EXTEND:
1578     case ISD::SIGN_EXTEND:
1579     case ISD::ZERO_EXTEND:
1580     case ISD::ANY_EXTEND:
1581     case ISD::FTRUNC:
1582     case ISD::FCANONICALIZE:
1583       Res = SplitVecOp_UnaryOp(N);
1584       break;
1585
1586     case ISD::ANY_EXTEND_VECTOR_INREG:
1587     case ISD::SIGN_EXTEND_VECTOR_INREG:
1588     case ISD::ZERO_EXTEND_VECTOR_INREG:
1589       Res = SplitVecOp_ExtVecInRegOp(N);
1590       break;
1591
1592     case ISD::VECREDUCE_FADD:
1593     case ISD::VECREDUCE_FMUL:
1594     case ISD::VECREDUCE_ADD:
1595     case ISD::VECREDUCE_MUL:
1596     case ISD::VECREDUCE_AND:
1597     case ISD::VECREDUCE_OR:
1598     case ISD::VECREDUCE_XOR:
1599     case ISD::VECREDUCE_SMAX:
1600     case ISD::VECREDUCE_SMIN:
1601     case ISD::VECREDUCE_UMAX:
1602     case ISD::VECREDUCE_UMIN:
1603     case ISD::VECREDUCE_FMAX:
1604     case ISD::VECREDUCE_FMIN:
1605       Res = SplitVecOp_VECREDUCE(N, OpNo);
1606       break;
1607     }
1608   }
1609
1610   // If the result is null, the sub-method took care of registering results etc.
1611   if (!Res.getNode()) return false;
1612
1613   // If the result is N, the sub-method updated N in place.  Tell the legalizer
1614   // core about this.
1615   if (Res.getNode() == N)
1616     return true;
1617
1618   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1619          "Invalid operand expansion");
1620
1621   ReplaceValueWith(SDValue(N, 0), Res);
1622   return false;
1623 }
1624
1625 SDValue DAGTypeLegalizer::SplitVecOp_VSELECT(SDNode *N, unsigned OpNo) {
1626   // The only possibility for an illegal operand is the mask, since result type
1627   // legalization would have handled this node already otherwise.
1628   assert(OpNo == 0 && "Illegal operand must be mask");
1629
1630   SDValue Mask = N->getOperand(0);
1631   SDValue Src0 = N->getOperand(1);
1632   SDValue Src1 = N->getOperand(2);
1633   EVT Src0VT = Src0.getValueType();
1634   SDLoc DL(N);
1635   assert(Mask.getValueType().isVector() && "VSELECT without a vector mask?");
1636
1637   SDValue Lo, Hi;
1638   GetSplitVector(N->getOperand(0), Lo, Hi);
1639   assert(Lo.getValueType() == Hi.getValueType() &&
1640          "Lo and Hi have differing types");
1641
1642   EVT LoOpVT, HiOpVT;
1643   std::tie(LoOpVT, HiOpVT) = DAG.GetSplitDestVTs(Src0VT);
1644   assert(LoOpVT == HiOpVT && "Asymmetric vector split?");
1645
1646   SDValue LoOp0, HiOp0, LoOp1, HiOp1, LoMask, HiMask;
1647   std::tie(LoOp0, HiOp0) = DAG.SplitVector(Src0, DL);
1648   std::tie(LoOp1, HiOp1) = DAG.SplitVector(Src1, DL);
1649   std::tie(LoMask, HiMask) = DAG.SplitVector(Mask, DL);
1650
1651   SDValue LoSelect =
1652     DAG.getNode(ISD::VSELECT, DL, LoOpVT, LoMask, LoOp0, LoOp1);
1653   SDValue HiSelect =
1654     DAG.getNode(ISD::VSELECT, DL, HiOpVT, HiMask, HiOp0, HiOp1);
1655
1656   return DAG.getNode(ISD::CONCAT_VECTORS, DL, Src0VT, LoSelect, HiSelect);
1657 }
1658
1659 SDValue DAGTypeLegalizer::SplitVecOp_VECREDUCE(SDNode *N, unsigned OpNo) {
1660   EVT ResVT = N->getValueType(0);
1661   SDValue Lo, Hi;
1662   SDLoc dl(N);
1663
1664   SDValue VecOp = N->getOperand(OpNo);
1665   EVT VecVT = VecOp.getValueType();
1666   assert(VecVT.isVector() && "Can only split reduce vector operand");
1667   GetSplitVector(VecOp, Lo, Hi);
1668   EVT LoOpVT, HiOpVT;
1669   std::tie(LoOpVT, HiOpVT) = DAG.GetSplitDestVTs(VecVT);
1670
1671   bool NoNaN = N->getFlags().hasNoNaNs();
1672   unsigned CombineOpc = 0;
1673   switch (N->getOpcode()) {
1674   case ISD::VECREDUCE_FADD: CombineOpc = ISD::FADD; break;
1675   case ISD::VECREDUCE_FMUL: CombineOpc = ISD::FMUL; break;
1676   case ISD::VECREDUCE_ADD:  CombineOpc = ISD::ADD; break;
1677   case ISD::VECREDUCE_MUL:  CombineOpc = ISD::MUL; break;
1678   case ISD::VECREDUCE_AND:  CombineOpc = ISD::AND; break;
1679   case ISD::VECREDUCE_OR:   CombineOpc = ISD::OR; break;
1680   case ISD::VECREDUCE_XOR:  CombineOpc = ISD::XOR; break;
1681   case ISD::VECREDUCE_SMAX: CombineOpc = ISD::SMAX; break;
1682   case ISD::VECREDUCE_SMIN: CombineOpc = ISD::SMIN; break;
1683   case ISD::VECREDUCE_UMAX: CombineOpc = ISD::UMAX; break;
1684   case ISD::VECREDUCE_UMIN: CombineOpc = ISD::UMIN; break;
1685   case ISD::VECREDUCE_FMAX:
1686     CombineOpc = NoNaN ? ISD::FMAXNUM : ISD::FMAXNAN;
1687     break;
1688   case ISD::VECREDUCE_FMIN:
1689     CombineOpc = NoNaN ? ISD::FMINNUM : ISD::FMINNAN;
1690     break;
1691   default:
1692     llvm_unreachable("Unexpected reduce ISD node");
1693   }
1694
1695   // Use the appropriate scalar instruction on the split subvectors before
1696   // reducing the now partially reduced smaller vector.
1697   SDValue Partial = DAG.getNode(CombineOpc, dl, LoOpVT, Lo, Hi, N->getFlags());
1698   return DAG.getNode(N->getOpcode(), dl, ResVT, Partial, N->getFlags());
1699 }
1700
1701 SDValue DAGTypeLegalizer::SplitVecOp_UnaryOp(SDNode *N) {
1702   // The result has a legal vector type, but the input needs splitting.
1703   EVT ResVT = N->getValueType(0);
1704   SDValue Lo, Hi;
1705   SDLoc dl(N);
1706   GetSplitVector(N->getOperand(0), Lo, Hi);
1707   EVT InVT = Lo.getValueType();
1708
1709   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
1710                                InVT.getVectorNumElements());
1711
1712   Lo = DAG.getNode(N->getOpcode(), dl, OutVT, Lo);
1713   Hi = DAG.getNode(N->getOpcode(), dl, OutVT, Hi);
1714
1715   return DAG.getNode(ISD::CONCAT_VECTORS, dl, ResVT, Lo, Hi);
1716 }
1717
1718 SDValue DAGTypeLegalizer::SplitVecOp_BITCAST(SDNode *N) {
1719   // For example, i64 = BITCAST v4i16 on alpha.  Typically the vector will
1720   // end up being split all the way down to individual components.  Convert the
1721   // split pieces into integers and reassemble.
1722   SDValue Lo, Hi;
1723   GetSplitVector(N->getOperand(0), Lo, Hi);
1724   Lo = BitConvertToInteger(Lo);
1725   Hi = BitConvertToInteger(Hi);
1726
1727   if (DAG.getDataLayout().isBigEndian())
1728     std::swap(Lo, Hi);
1729
1730   return DAG.getNode(ISD::BITCAST, SDLoc(N), N->getValueType(0),
1731                      JoinIntegers(Lo, Hi));
1732 }
1733
1734 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
1735   // We know that the extracted result type is legal.
1736   EVT SubVT = N->getValueType(0);
1737   SDValue Idx = N->getOperand(1);
1738   SDLoc dl(N);
1739   SDValue Lo, Hi;
1740   GetSplitVector(N->getOperand(0), Lo, Hi);
1741
1742   uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1743   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1744
1745   if (IdxVal < LoElts) {
1746     assert(IdxVal + SubVT.getVectorNumElements() <= LoElts &&
1747            "Extracted subvector crosses vector split!");
1748     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Lo, Idx);
1749   } else {
1750     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Hi,
1751                        DAG.getConstant(IdxVal - LoElts, dl,
1752                                        Idx.getValueType()));
1753   }
1754 }
1755
1756 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
1757   SDValue Vec = N->getOperand(0);
1758   SDValue Idx = N->getOperand(1);
1759   EVT VecVT = Vec.getValueType();
1760
1761   if (isa<ConstantSDNode>(Idx)) {
1762     uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1763     assert(IdxVal < VecVT.getVectorNumElements() && "Invalid vector index!");
1764
1765     SDValue Lo, Hi;
1766     GetSplitVector(Vec, Lo, Hi);
1767
1768     uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1769
1770     if (IdxVal < LoElts)
1771       return SDValue(DAG.UpdateNodeOperands(N, Lo, Idx), 0);
1772     return SDValue(DAG.UpdateNodeOperands(N, Hi,
1773                                   DAG.getConstant(IdxVal - LoElts, SDLoc(N),
1774                                                   Idx.getValueType())), 0);
1775   }
1776
1777   // See if the target wants to custom expand this node.
1778   if (CustomLowerNode(N, N->getValueType(0), true))
1779     return SDValue();
1780
1781   // Make the vector elements byte-addressable if they aren't already.
1782   SDLoc dl(N);
1783   EVT EltVT = VecVT.getVectorElementType();
1784   if (VecVT.getScalarSizeInBits() < 8) {
1785     EltVT = MVT::i8;
1786     VecVT = EVT::getVectorVT(*DAG.getContext(), EltVT,
1787                              VecVT.getVectorNumElements());
1788     Vec = DAG.getNode(ISD::ANY_EXTEND, dl, VecVT, Vec);
1789   }
1790
1791   // Store the vector to the stack.
1792   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
1793   auto &MF = DAG.getMachineFunction();
1794   auto FrameIndex = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
1795   auto PtrInfo = MachinePointerInfo::getFixedStack(MF, FrameIndex);
1796   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, PtrInfo);
1797
1798   // Load back the required element.
1799   StackPtr = TLI.getVectorElementPointer(DAG, StackPtr, VecVT, Idx);
1800   return DAG.getExtLoad(
1801       ISD::EXTLOAD, dl, N->getValueType(0), Store, StackPtr,
1802       MachinePointerInfo::getUnknownStack(DAG.getMachineFunction()), EltVT);
1803 }
1804
1805 SDValue DAGTypeLegalizer::SplitVecOp_ExtVecInRegOp(SDNode *N) {
1806   SDValue Lo, Hi;
1807
1808   // *_EXTEND_VECTOR_INREG only reference the lower half of the input, so
1809   // splitting the result has the same effect as splitting the input operand.
1810   SplitVecRes_ExtVecInRegOp(N, Lo, Hi);
1811
1812   return DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(N), N->getValueType(0), Lo, Hi);
1813 }
1814
1815 SDValue DAGTypeLegalizer::SplitVecOp_MGATHER(MaskedGatherSDNode *MGT,
1816                                              unsigned OpNo) {
1817   EVT LoVT, HiVT;
1818   SDLoc dl(MGT);
1819   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(MGT->getValueType(0));
1820
1821   SDValue Ch = MGT->getChain();
1822   SDValue Ptr = MGT->getBasePtr();
1823   SDValue Index = MGT->getIndex();
1824   SDValue Scale = MGT->getScale();
1825   SDValue Mask = MGT->getMask();
1826   SDValue Src0 = MGT->getValue();
1827   unsigned Alignment = MGT->getOriginalAlignment();
1828
1829   SDValue MaskLo, MaskHi;
1830   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1831     // Split Mask operand
1832     GetSplitVector(Mask, MaskLo, MaskHi);
1833   else
1834     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, dl);
1835
1836   EVT MemoryVT = MGT->getMemoryVT();
1837   EVT LoMemVT, HiMemVT;
1838   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1839
1840   SDValue Src0Lo, Src0Hi;
1841   if (getTypeAction(Src0.getValueType()) == TargetLowering::TypeSplitVector)
1842     GetSplitVector(Src0, Src0Lo, Src0Hi);
1843   else
1844     std::tie(Src0Lo, Src0Hi) = DAG.SplitVector(Src0, dl);
1845
1846   SDValue IndexHi, IndexLo;
1847   if (getTypeAction(Index.getValueType()) == TargetLowering::TypeSplitVector)
1848     GetSplitVector(Index, IndexLo, IndexHi);
1849   else
1850     std::tie(IndexLo, IndexHi) = DAG.SplitVector(Index, dl);
1851
1852   MachineMemOperand *MMO = DAG.getMachineFunction().
1853     getMachineMemOperand(MGT->getPointerInfo(),
1854                          MachineMemOperand::MOLoad,  LoMemVT.getStoreSize(),
1855                          Alignment, MGT->getAAInfo(), MGT->getRanges());
1856
1857   SDValue OpsLo[] = {Ch, Src0Lo, MaskLo, Ptr, IndexLo, Scale};
1858   SDValue Lo = DAG.getMaskedGather(DAG.getVTList(LoVT, MVT::Other), LoVT, dl,
1859                                    OpsLo, MMO);
1860
1861   MMO = DAG.getMachineFunction().
1862     getMachineMemOperand(MGT->getPointerInfo(),
1863                          MachineMemOperand::MOLoad,  HiMemVT.getStoreSize(),
1864                          Alignment, MGT->getAAInfo(),
1865                          MGT->getRanges());
1866
1867   SDValue OpsHi[] = {Ch, Src0Hi, MaskHi, Ptr, IndexHi, Scale};
1868   SDValue Hi = DAG.getMaskedGather(DAG.getVTList(HiVT, MVT::Other), HiVT, dl,
1869                                    OpsHi, MMO);
1870
1871   // Build a factor node to remember that this load is independent of the
1872   // other one.
1873   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1874                    Hi.getValue(1));
1875
1876   // Legalize the chain result - switch anything that used the old chain to
1877   // use the new one.
1878   ReplaceValueWith(SDValue(MGT, 1), Ch);
1879
1880   SDValue Res = DAG.getNode(ISD::CONCAT_VECTORS, dl, MGT->getValueType(0), Lo,
1881                             Hi);
1882   ReplaceValueWith(SDValue(MGT, 0), Res);
1883   return SDValue();
1884 }
1885
1886 SDValue DAGTypeLegalizer::SplitVecOp_MSTORE(MaskedStoreSDNode *N,
1887                                             unsigned OpNo) {
1888   SDValue Ch  = N->getChain();
1889   SDValue Ptr = N->getBasePtr();
1890   SDValue Mask = N->getMask();
1891   SDValue Data = N->getValue();
1892   EVT MemoryVT = N->getMemoryVT();
1893   unsigned Alignment = N->getOriginalAlignment();
1894   SDLoc DL(N);
1895
1896   EVT LoMemVT, HiMemVT;
1897   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1898
1899   SDValue DataLo, DataHi;
1900   if (getTypeAction(Data.getValueType()) == TargetLowering::TypeSplitVector)
1901     // Split Data operand
1902     GetSplitVector(Data, DataLo, DataHi);
1903   else
1904     std::tie(DataLo, DataHi) = DAG.SplitVector(Data, DL);
1905
1906   SDValue MaskLo, MaskHi;
1907   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1908     // Split Mask operand
1909     GetSplitVector(Mask, MaskLo, MaskHi);
1910   else
1911     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, DL);
1912
1913   // if Alignment is equal to the vector size,
1914   // take the half of it for the second part
1915   unsigned SecondHalfAlignment =
1916     (Alignment == Data->getValueType(0).getSizeInBits()/8) ?
1917        Alignment/2 : Alignment;
1918
1919   SDValue Lo, Hi;
1920   MachineMemOperand *MMO = DAG.getMachineFunction().
1921     getMachineMemOperand(N->getPointerInfo(),
1922                          MachineMemOperand::MOStore, LoMemVT.getStoreSize(),
1923                          Alignment, N->getAAInfo(), N->getRanges());
1924
1925   Lo = DAG.getMaskedStore(Ch, DL, DataLo, Ptr, MaskLo, LoMemVT, MMO,
1926                           N->isTruncatingStore(),
1927                           N->isCompressingStore());
1928
1929   Ptr = TLI.IncrementMemoryAddress(Ptr, MaskLo, DL, LoMemVT, DAG,
1930                                    N->isCompressingStore());
1931   unsigned HiOffset = LoMemVT.getStoreSize();
1932
1933   MMO = DAG.getMachineFunction().getMachineMemOperand(
1934       N->getPointerInfo().getWithOffset(HiOffset), MachineMemOperand::MOStore,
1935       HiMemVT.getStoreSize(), SecondHalfAlignment, N->getAAInfo(),
1936       N->getRanges());
1937
1938   Hi = DAG.getMaskedStore(Ch, DL, DataHi, Ptr, MaskHi, HiMemVT, MMO,
1939                           N->isTruncatingStore(), N->isCompressingStore());
1940
1941   // Build a factor node to remember that this store is independent of the
1942   // other one.
1943   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
1944 }
1945
1946 SDValue DAGTypeLegalizer::SplitVecOp_MSCATTER(MaskedScatterSDNode *N,
1947                                               unsigned OpNo) {
1948   SDValue Ch  = N->getChain();
1949   SDValue Ptr = N->getBasePtr();
1950   SDValue Mask = N->getMask();
1951   SDValue Index = N->getIndex();
1952   SDValue Scale = N->getScale();
1953   SDValue Data = N->getValue();
1954   EVT MemoryVT = N->getMemoryVT();
1955   unsigned Alignment = N->getOriginalAlignment();
1956   SDLoc DL(N);
1957
1958   // Split all operands
1959   EVT LoMemVT, HiMemVT;
1960   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1961
1962   SDValue DataLo, DataHi;
1963   if (getTypeAction(Data.getValueType()) == TargetLowering::TypeSplitVector)
1964     // Split Data operand
1965     GetSplitVector(Data, DataLo, DataHi);
1966   else
1967     std::tie(DataLo, DataHi) = DAG.SplitVector(Data, DL);
1968
1969   SDValue MaskLo, MaskHi;
1970   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1971     // Split Mask operand
1972     GetSplitVector(Mask, MaskLo, MaskHi);
1973   else
1974     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, DL);
1975
1976   SDValue IndexHi, IndexLo;
1977   if (getTypeAction(Index.getValueType()) == TargetLowering::TypeSplitVector)
1978     GetSplitVector(Index, IndexLo, IndexHi);
1979   else
1980     std::tie(IndexLo, IndexHi) = DAG.SplitVector(Index, DL);
1981
1982   SDValue Lo;
1983   MachineMemOperand *MMO = DAG.getMachineFunction().
1984     getMachineMemOperand(N->getPointerInfo(),
1985                          MachineMemOperand::MOStore, LoMemVT.getStoreSize(),
1986                          Alignment, N->getAAInfo(), N->getRanges());
1987
1988   SDValue OpsLo[] = {Ch, DataLo, MaskLo, Ptr, IndexLo, Scale};
1989   Lo = DAG.getMaskedScatter(DAG.getVTList(MVT::Other), DataLo.getValueType(),
1990                             DL, OpsLo, MMO);
1991
1992   MMO = DAG.getMachineFunction().
1993     getMachineMemOperand(N->getPointerInfo(),
1994                          MachineMemOperand::MOStore,  HiMemVT.getStoreSize(),
1995                          Alignment, N->getAAInfo(), N->getRanges());
1996
1997   // The order of the Scatter operation after split is well defined. The "Hi"
1998   // part comes after the "Lo". So these two operations should be chained one
1999   // after another.
2000   SDValue OpsHi[] = {Lo, DataHi, MaskHi, Ptr, IndexHi, Scale};
2001   return DAG.getMaskedScatter(DAG.getVTList(MVT::Other), DataHi.getValueType(),
2002                               DL, OpsHi, MMO);
2003 }
2004
2005 SDValue DAGTypeLegalizer::SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo) {
2006   assert(N->isUnindexed() && "Indexed store of vector?");
2007   assert(OpNo == 1 && "Can only split the stored value");
2008   SDLoc DL(N);
2009
2010   bool isTruncating = N->isTruncatingStore();
2011   SDValue Ch  = N->getChain();
2012   SDValue Ptr = N->getBasePtr();
2013   EVT MemoryVT = N->getMemoryVT();
2014   unsigned Alignment = N->getOriginalAlignment();
2015   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
2016   AAMDNodes AAInfo = N->getAAInfo();
2017   SDValue Lo, Hi;
2018   GetSplitVector(N->getOperand(1), Lo, Hi);
2019
2020   EVT LoMemVT, HiMemVT;
2021   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
2022
2023   // Scalarize if the split halves are not byte-sized.
2024   if (!LoMemVT.isByteSized() || !HiMemVT.isByteSized())
2025     return TLI.scalarizeVectorStore(N, DAG);
2026
2027   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
2028
2029   if (isTruncating)
2030     Lo = DAG.getTruncStore(Ch, DL, Lo, Ptr, N->getPointerInfo(), LoMemVT,
2031                            Alignment, MMOFlags, AAInfo);
2032   else
2033     Lo = DAG.getStore(Ch, DL, Lo, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
2034                       AAInfo);
2035
2036   // Increment the pointer to the other half.
2037   Ptr = DAG.getObjectPtrOffset(DL, Ptr, IncrementSize);
2038
2039   if (isTruncating)
2040     Hi = DAG.getTruncStore(Ch, DL, Hi, Ptr,
2041                            N->getPointerInfo().getWithOffset(IncrementSize),
2042                            HiMemVT, Alignment, MMOFlags, AAInfo);
2043   else
2044     Hi = DAG.getStore(Ch, DL, Hi, Ptr,
2045                       N->getPointerInfo().getWithOffset(IncrementSize),
2046                       Alignment, MMOFlags, AAInfo);
2047
2048   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
2049 }
2050
2051 SDValue DAGTypeLegalizer::SplitVecOp_CONCAT_VECTORS(SDNode *N) {
2052   SDLoc DL(N);
2053
2054   // The input operands all must have the same type, and we know the result
2055   // type is valid.  Convert this to a buildvector which extracts all the
2056   // input elements.
2057   // TODO: If the input elements are power-two vectors, we could convert this to
2058   // a new CONCAT_VECTORS node with elements that are half-wide.
2059   SmallVector<SDValue, 32> Elts;
2060   EVT EltVT = N->getValueType(0).getVectorElementType();
2061   for (const SDValue &Op : N->op_values()) {
2062     for (unsigned i = 0, e = Op.getValueType().getVectorNumElements();
2063          i != e; ++i) {
2064       Elts.push_back(DAG.getNode(
2065           ISD::EXTRACT_VECTOR_ELT, DL, EltVT, Op,
2066           DAG.getConstant(i, DL, TLI.getVectorIdxTy(DAG.getDataLayout()))));
2067     }
2068   }
2069
2070   return DAG.getBuildVector(N->getValueType(0), DL, Elts);
2071 }
2072
2073 SDValue DAGTypeLegalizer::SplitVecOp_TruncateHelper(SDNode *N) {
2074   // The result type is legal, but the input type is illegal.  If splitting
2075   // ends up with the result type of each half still being legal, just
2076   // do that.  If, however, that would result in an illegal result type,
2077   // we can try to get more clever with power-two vectors. Specifically,
2078   // split the input type, but also widen the result element size, then
2079   // concatenate the halves and truncate again.  For example, consider a target
2080   // where v8i8 is legal and v8i32 is not (ARM, which doesn't have 256-bit
2081   // vectors). To perform a "%res = v8i8 trunc v8i32 %in" we do:
2082   //   %inlo = v4i32 extract_subvector %in, 0
2083   //   %inhi = v4i32 extract_subvector %in, 4
2084   //   %lo16 = v4i16 trunc v4i32 %inlo
2085   //   %hi16 = v4i16 trunc v4i32 %inhi
2086   //   %in16 = v8i16 concat_vectors v4i16 %lo16, v4i16 %hi16
2087   //   %res = v8i8 trunc v8i16 %in16
2088   //
2089   // Without this transform, the original truncate would end up being
2090   // scalarized, which is pretty much always a last resort.
2091   SDValue InVec = N->getOperand(0);
2092   EVT InVT = InVec->getValueType(0);
2093   EVT OutVT = N->getValueType(0);
2094   unsigned NumElements = OutVT.getVectorNumElements();
2095   bool IsFloat = OutVT.isFloatingPoint();
2096
2097   // Widening should have already made sure this is a power-two vector
2098   // if we're trying to split it at all. assert() that's true, just in case.
2099   assert(!(NumElements & 1) && "Splitting vector, but not in half!");
2100
2101   unsigned InElementSize = InVT.getScalarSizeInBits();
2102   unsigned OutElementSize = OutVT.getScalarSizeInBits();
2103
2104   // If the input elements are only 1/2 the width of the result elements,
2105   // just use the normal splitting. Our trick only work if there's room
2106   // to split more than once.
2107   if (InElementSize <= OutElementSize * 2)
2108     return SplitVecOp_UnaryOp(N);
2109   SDLoc DL(N);
2110
2111   // Extract the halves of the input via extract_subvector.
2112   SDValue InLoVec, InHiVec;
2113   std::tie(InLoVec, InHiVec) = DAG.SplitVector(InVec, DL);
2114   // Truncate them to 1/2 the element size.
2115   EVT HalfElementVT = IsFloat ?
2116     EVT::getFloatingPointVT(InElementSize/2) :
2117     EVT::getIntegerVT(*DAG.getContext(), InElementSize/2);
2118   EVT HalfVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT,
2119                                 NumElements/2);
2120   SDValue HalfLo = DAG.getNode(N->getOpcode(), DL, HalfVT, InLoVec);
2121   SDValue HalfHi = DAG.getNode(N->getOpcode(), DL, HalfVT, InHiVec);
2122   // Concatenate them to get the full intermediate truncation result.
2123   EVT InterVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT, NumElements);
2124   SDValue InterVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InterVT, HalfLo,
2125                                  HalfHi);
2126   // Now finish up by truncating all the way down to the original result
2127   // type. This should normally be something that ends up being legal directly,
2128   // but in theory if a target has very wide vectors and an annoyingly
2129   // restricted set of legal types, this split can chain to build things up.
2130   return IsFloat
2131              ? DAG.getNode(ISD::FP_ROUND, DL, OutVT, InterVec,
2132                            DAG.getTargetConstant(
2133                                0, DL, TLI.getPointerTy(DAG.getDataLayout())))
2134              : DAG.getNode(ISD::TRUNCATE, DL, OutVT, InterVec);
2135 }
2136
2137 SDValue DAGTypeLegalizer::SplitVecOp_VSETCC(SDNode *N) {
2138   assert(N->getValueType(0).isVector() &&
2139          N->getOperand(0).getValueType().isVector() &&
2140          "Operand types must be vectors");
2141   // The result has a legal vector type, but the input needs splitting.
2142   SDValue Lo0, Hi0, Lo1, Hi1, LoRes, HiRes;
2143   SDLoc DL(N);
2144   GetSplitVector(N->getOperand(0), Lo0, Hi0);
2145   GetSplitVector(N->getOperand(1), Lo1, Hi1);
2146   unsigned PartElements = Lo0.getValueType().getVectorNumElements();
2147   EVT PartResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, PartElements);
2148   EVT WideResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, 2*PartElements);
2149
2150   LoRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Lo0, Lo1, N->getOperand(2));
2151   HiRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Hi0, Hi1, N->getOperand(2));
2152   SDValue Con = DAG.getNode(ISD::CONCAT_VECTORS, DL, WideResVT, LoRes, HiRes);
2153   return PromoteTargetBoolean(Con, N->getValueType(0));
2154 }
2155
2156
2157 SDValue DAGTypeLegalizer::SplitVecOp_FP_ROUND(SDNode *N) {
2158   // The result has a legal vector type, but the input needs splitting.
2159   EVT ResVT = N->getValueType(0);
2160   SDValue Lo, Hi;
2161   SDLoc DL(N);
2162   GetSplitVector(N->getOperand(0), Lo, Hi);
2163   EVT InVT = Lo.getValueType();
2164
2165   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
2166                                InVT.getVectorNumElements());
2167
2168   Lo = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Lo, N->getOperand(1));
2169   Hi = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Hi, N->getOperand(1));
2170
2171   return DAG.getNode(ISD::CONCAT_VECTORS, DL, ResVT, Lo, Hi);
2172 }
2173
2174 SDValue DAGTypeLegalizer::SplitVecOp_FCOPYSIGN(SDNode *N) {
2175   // The result (and the first input) has a legal vector type, but the second
2176   // input needs splitting.
2177   return DAG.UnrollVectorOp(N, N->getValueType(0).getVectorNumElements());
2178 }
2179
2180
2181 //===----------------------------------------------------------------------===//
2182 //  Result Vector Widening
2183 //===----------------------------------------------------------------------===//
2184
2185 void DAGTypeLegalizer::WidenVectorResult(SDNode *N, unsigned ResNo) {
2186   DEBUG(dbgs() << "Widen node result " << ResNo << ": ";
2187         N->dump(&DAG);
2188         dbgs() << "\n");
2189
2190   // See if the target wants to custom widen this node.
2191   if (CustomWidenLowerNode(N, N->getValueType(ResNo)))
2192     return;
2193
2194   SDValue Res = SDValue();
2195   switch (N->getOpcode()) {
2196   default:
2197 #ifndef NDEBUG
2198     dbgs() << "WidenVectorResult #" << ResNo << ": ";
2199     N->dump(&DAG);
2200     dbgs() << "\n";
2201 #endif
2202     llvm_unreachable("Do not know how to widen the result of this operator!");
2203
2204   case ISD::MERGE_VALUES:      Res = WidenVecRes_MERGE_VALUES(N, ResNo); break;
2205   case ISD::BITCAST:           Res = WidenVecRes_BITCAST(N); break;
2206   case ISD::BUILD_VECTOR:      Res = WidenVecRes_BUILD_VECTOR(N); break;
2207   case ISD::CONCAT_VECTORS:    Res = WidenVecRes_CONCAT_VECTORS(N); break;
2208   case ISD::EXTRACT_SUBVECTOR: Res = WidenVecRes_EXTRACT_SUBVECTOR(N); break;
2209   case ISD::FP_ROUND_INREG:    Res = WidenVecRes_InregOp(N); break;
2210   case ISD::INSERT_VECTOR_ELT: Res = WidenVecRes_INSERT_VECTOR_ELT(N); break;
2211   case ISD::LOAD:              Res = WidenVecRes_LOAD(N); break;
2212   case ISD::SCALAR_TO_VECTOR:  Res = WidenVecRes_SCALAR_TO_VECTOR(N); break;
2213   case ISD::SIGN_EXTEND_INREG: Res = WidenVecRes_InregOp(N); break;
2214   case ISD::VSELECT:
2215   case ISD::SELECT:            Res = WidenVecRes_SELECT(N); break;
2216   case ISD::SELECT_CC:         Res = WidenVecRes_SELECT_CC(N); break;
2217   case ISD::SETCC:             Res = WidenVecRes_SETCC(N); break;
2218   case ISD::UNDEF:             Res = WidenVecRes_UNDEF(N); break;
2219   case ISD::VECTOR_SHUFFLE:
2220     Res = WidenVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N));
2221     break;
2222   case ISD::MLOAD:
2223     Res = WidenVecRes_MLOAD(cast<MaskedLoadSDNode>(N));
2224     break;
2225   case ISD::MGATHER:
2226     Res = WidenVecRes_MGATHER(cast<MaskedGatherSDNode>(N));
2227     break;
2228
2229   case ISD::ADD:
2230   case ISD::AND:
2231   case ISD::MUL:
2232   case ISD::MULHS:
2233   case ISD::MULHU:
2234   case ISD::OR:
2235   case ISD::SUB:
2236   case ISD::XOR:
2237   case ISD::FMINNUM:
2238   case ISD::FMAXNUM:
2239   case ISD::FMINNAN:
2240   case ISD::FMAXNAN:
2241   case ISD::SMIN:
2242   case ISD::SMAX:
2243   case ISD::UMIN:
2244   case ISD::UMAX:
2245     Res = WidenVecRes_Binary(N);
2246     break;
2247
2248   case ISD::FADD:
2249   case ISD::FMUL:
2250   case ISD::FPOW:
2251   case ISD::FSUB:
2252   case ISD::FDIV:
2253   case ISD::FREM:
2254   case ISD::SDIV:
2255   case ISD::UDIV:
2256   case ISD::SREM:
2257   case ISD::UREM:
2258     Res = WidenVecRes_BinaryCanTrap(N);
2259     break;
2260
2261   case ISD::FCOPYSIGN:
2262     Res = WidenVecRes_FCOPYSIGN(N);
2263     break;
2264
2265   case ISD::FPOWI:
2266     Res = WidenVecRes_POWI(N);
2267     break;
2268
2269   case ISD::SHL:
2270   case ISD::SRA:
2271   case ISD::SRL:
2272     Res = WidenVecRes_Shift(N);
2273     break;
2274
2275   case ISD::ANY_EXTEND_VECTOR_INREG:
2276   case ISD::SIGN_EXTEND_VECTOR_INREG:
2277   case ISD::ZERO_EXTEND_VECTOR_INREG:
2278     Res = WidenVecRes_EXTEND_VECTOR_INREG(N);
2279     break;
2280
2281   case ISD::ANY_EXTEND:
2282   case ISD::FP_EXTEND:
2283   case ISD::FP_ROUND:
2284   case ISD::FP_TO_SINT:
2285   case ISD::FP_TO_UINT:
2286   case ISD::SIGN_EXTEND:
2287   case ISD::SINT_TO_FP:
2288   case ISD::TRUNCATE:
2289   case ISD::UINT_TO_FP:
2290   case ISD::ZERO_EXTEND:
2291     Res = WidenVecRes_Convert(N);
2292     break;
2293
2294   case ISD::BITREVERSE:
2295   case ISD::BSWAP:
2296   case ISD::CTLZ:
2297   case ISD::CTPOP:
2298   case ISD::CTTZ:
2299   case ISD::FABS:
2300   case ISD::FCEIL:
2301   case ISD::FCOS:
2302   case ISD::FEXP:
2303   case ISD::FEXP2:
2304   case ISD::FFLOOR:
2305   case ISD::FLOG:
2306   case ISD::FLOG10:
2307   case ISD::FLOG2:
2308   case ISD::FNEARBYINT:
2309   case ISD::FNEG:
2310   case ISD::FRINT:
2311   case ISD::FROUND:
2312   case ISD::FSIN:
2313   case ISD::FSQRT:
2314   case ISD::FTRUNC:
2315     Res = WidenVecRes_Unary(N);
2316     break;
2317   case ISD::FMA:
2318     Res = WidenVecRes_Ternary(N);
2319     break;
2320   }
2321
2322   // If Res is null, the sub-method took care of registering the result.
2323   if (Res.getNode())
2324     SetWidenedVector(SDValue(N, ResNo), Res);
2325 }
2326
2327 SDValue DAGTypeLegalizer::WidenVecRes_Ternary(SDNode *N) {
2328   // Ternary op widening.
2329   SDLoc dl(N);
2330   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2331   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2332   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2333   SDValue InOp3 = GetWidenedVector(N->getOperand(2));
2334   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, InOp3);
2335 }
2336
2337 SDValue DAGTypeLegalizer::WidenVecRes_Binary(SDNode *N) {
2338   // Binary op widening.
2339   SDLoc dl(N);
2340   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2341   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2342   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2343   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, N->getFlags());
2344 }
2345
2346 SDValue DAGTypeLegalizer::WidenVecRes_BinaryCanTrap(SDNode *N) {
2347   // Binary op widening for operations that can trap.
2348   unsigned Opcode = N->getOpcode();
2349   SDLoc dl(N);
2350   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2351   EVT WidenEltVT = WidenVT.getVectorElementType();
2352   EVT VT = WidenVT;
2353   unsigned NumElts =  VT.getVectorNumElements();
2354   const SDNodeFlags Flags = N->getFlags();
2355   while (!TLI.isTypeLegal(VT) && NumElts != 1) {
2356     NumElts = NumElts / 2;
2357     VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
2358   }
2359
2360   if (NumElts != 1 && !TLI.canOpTrap(N->getOpcode(), VT)) {
2361     // Operation doesn't trap so just widen as normal.
2362     SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2363     SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2364     return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, Flags);
2365   }
2366
2367   // No legal vector version so unroll the vector operation and then widen.
2368   if (NumElts == 1)
2369     return DAG.UnrollVectorOp(N, WidenVT.getVectorNumElements());
2370
2371   // Since the operation can trap, apply operation on the original vector.
2372   EVT MaxVT = VT;
2373   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2374   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2375   unsigned CurNumElts = N->getValueType(0).getVectorNumElements();
2376
2377   SmallVector<SDValue, 16> ConcatOps(CurNumElts);
2378   unsigned ConcatEnd = 0;  // Current ConcatOps index.
2379   int Idx = 0;        // Current Idx into input vectors.
2380
2381   // NumElts := greatest legal vector size (at most WidenVT)
2382   // while (orig. vector has unhandled elements) {
2383   //   take munches of size NumElts from the beginning and add to ConcatOps
2384   //   NumElts := next smaller supported vector size or 1
2385   // }
2386   while (CurNumElts != 0) {
2387     while (CurNumElts >= NumElts) {
2388       SDValue EOp1 = DAG.getNode(
2389           ISD::EXTRACT_SUBVECTOR, dl, VT, InOp1,
2390           DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2391       SDValue EOp2 = DAG.getNode(
2392           ISD::EXTRACT_SUBVECTOR, dl, VT, InOp2,
2393           DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2394       ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, VT, EOp1, EOp2, Flags);
2395       Idx += NumElts;
2396       CurNumElts -= NumElts;
2397     }
2398     do {
2399       NumElts = NumElts / 2;
2400       VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
2401     } while (!TLI.isTypeLegal(VT) && NumElts != 1);
2402
2403     if (NumElts == 1) {
2404       for (unsigned i = 0; i != CurNumElts; ++i, ++Idx) {
2405         SDValue EOp1 = DAG.getNode(
2406             ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT, InOp1,
2407             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2408         SDValue EOp2 = DAG.getNode(
2409             ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT, InOp2,
2410             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2411         ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, WidenEltVT,
2412                                              EOp1, EOp2, Flags);
2413       }
2414       CurNumElts = 0;
2415     }
2416   }
2417
2418   // Check to see if we have a single operation with the widen type.
2419   if (ConcatEnd == 1) {
2420     VT = ConcatOps[0].getValueType();
2421     if (VT == WidenVT)
2422       return ConcatOps[0];
2423   }
2424
2425   // while (Some element of ConcatOps is not of type MaxVT) {
2426   //   From the end of ConcatOps, collect elements of the same type and put
2427   //   them into an op of the next larger supported type
2428   // }
2429   while (ConcatOps[ConcatEnd-1].getValueType() != MaxVT) {
2430     Idx = ConcatEnd - 1;
2431     VT = ConcatOps[Idx--].getValueType();
2432     while (Idx >= 0 && ConcatOps[Idx].getValueType() == VT)
2433       Idx--;
2434
2435     int NextSize = VT.isVector() ? VT.getVectorNumElements() : 1;
2436     EVT NextVT;
2437     do {
2438       NextSize *= 2;
2439       NextVT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NextSize);
2440     } while (!TLI.isTypeLegal(NextVT));
2441
2442     if (!VT.isVector()) {
2443       // Scalar type, create an INSERT_VECTOR_ELEMENT of type NextVT
2444       SDValue VecOp = DAG.getUNDEF(NextVT);
2445       unsigned NumToInsert = ConcatEnd - Idx - 1;
2446       for (unsigned i = 0, OpIdx = Idx+1; i < NumToInsert; i++, OpIdx++) {
2447         VecOp = DAG.getNode(
2448             ISD::INSERT_VECTOR_ELT, dl, NextVT, VecOp, ConcatOps[OpIdx],
2449             DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2450       }
2451       ConcatOps[Idx+1] = VecOp;
2452       ConcatEnd = Idx + 2;
2453     } else {
2454       // Vector type, create a CONCAT_VECTORS of type NextVT
2455       SDValue undefVec = DAG.getUNDEF(VT);
2456       unsigned OpsToConcat = NextSize/VT.getVectorNumElements();
2457       SmallVector<SDValue, 16> SubConcatOps(OpsToConcat);
2458       unsigned RealVals = ConcatEnd - Idx - 1;
2459       unsigned SubConcatEnd = 0;
2460       unsigned SubConcatIdx = Idx + 1;
2461       while (SubConcatEnd < RealVals)
2462         SubConcatOps[SubConcatEnd++] = ConcatOps[++Idx];
2463       while (SubConcatEnd < OpsToConcat)
2464         SubConcatOps[SubConcatEnd++] = undefVec;
2465       ConcatOps[SubConcatIdx] = DAG.getNode(ISD::CONCAT_VECTORS, dl,
2466                                             NextVT, SubConcatOps);
2467       ConcatEnd = SubConcatIdx + 1;
2468     }
2469   }
2470
2471   // Check to see if we have a single operation with the widen type.
2472   if (ConcatEnd == 1) {
2473     VT = ConcatOps[0].getValueType();
2474     if (VT == WidenVT)
2475       return ConcatOps[0];
2476   }
2477
2478   // add undefs of size MaxVT until ConcatOps grows to length of WidenVT
2479   unsigned NumOps = WidenVT.getVectorNumElements()/MaxVT.getVectorNumElements();
2480   if (NumOps != ConcatEnd ) {
2481     SDValue UndefVal = DAG.getUNDEF(MaxVT);
2482     for (unsigned j = ConcatEnd; j < NumOps; ++j)
2483       ConcatOps[j] = UndefVal;
2484   }
2485   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
2486                      makeArrayRef(ConcatOps.data(), NumOps));
2487 }
2488
2489 SDValue DAGTypeLegalizer::WidenVecRes_Convert(SDNode *N) {
2490   SDValue InOp = N->getOperand(0);
2491   SDLoc DL(N);
2492
2493   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2494   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2495
2496   EVT InVT = InOp.getValueType();
2497   EVT InEltVT = InVT.getVectorElementType();
2498   EVT InWidenVT = EVT::getVectorVT(*DAG.getContext(), InEltVT, WidenNumElts);
2499
2500   unsigned Opcode = N->getOpcode();
2501   unsigned InVTNumElts = InVT.getVectorNumElements();
2502   const SDNodeFlags Flags = N->getFlags();
2503   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
2504     InOp = GetWidenedVector(N->getOperand(0));
2505     InVT = InOp.getValueType();
2506     InVTNumElts = InVT.getVectorNumElements();
2507     if (InVTNumElts == WidenNumElts) {
2508       if (N->getNumOperands() == 1)
2509         return DAG.getNode(Opcode, DL, WidenVT, InOp);
2510       return DAG.getNode(Opcode, DL, WidenVT, InOp, N->getOperand(1), Flags);
2511     }
2512     if (WidenVT.getSizeInBits() == InVT.getSizeInBits()) {
2513       // If both input and result vector types are of same width, extend
2514       // operations should be done with SIGN/ZERO_EXTEND_VECTOR_INREG, which
2515       // accepts fewer elements in the result than in the input.
2516       if (Opcode == ISD::SIGN_EXTEND)
2517         return DAG.getSignExtendVectorInReg(InOp, DL, WidenVT);
2518       if (Opcode == ISD::ZERO_EXTEND)
2519         return DAG.getZeroExtendVectorInReg(InOp, DL, WidenVT);
2520     }
2521   }
2522
2523   if (TLI.isTypeLegal(InWidenVT)) {
2524     // Because the result and the input are different vector types, widening
2525     // the result could create a legal type but widening the input might make
2526     // it an illegal type that might lead to repeatedly splitting the input
2527     // and then widening it. To avoid this, we widen the input only if
2528     // it results in a legal type.
2529     if (WidenNumElts % InVTNumElts == 0) {
2530       // Widen the input and call convert on the widened input vector.
2531       unsigned NumConcat = WidenNumElts/InVTNumElts;
2532       SmallVector<SDValue, 16> Ops(NumConcat);
2533       Ops[0] = InOp;
2534       SDValue UndefVal = DAG.getUNDEF(InVT);
2535       for (unsigned i = 1; i != NumConcat; ++i)
2536         Ops[i] = UndefVal;
2537       SDValue InVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InWidenVT, Ops);
2538       if (N->getNumOperands() == 1)
2539         return DAG.getNode(Opcode, DL, WidenVT, InVec);
2540       return DAG.getNode(Opcode, DL, WidenVT, InVec, N->getOperand(1), Flags);
2541     }
2542
2543     if (InVTNumElts % WidenNumElts == 0) {
2544       SDValue InVal = DAG.getNode(
2545           ISD::EXTRACT_SUBVECTOR, DL, InWidenVT, InOp,
2546           DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
2547       // Extract the input and convert the shorten input vector.
2548       if (N->getNumOperands() == 1)
2549         return DAG.getNode(Opcode, DL, WidenVT, InVal);
2550       return DAG.getNode(Opcode, DL, WidenVT, InVal, N->getOperand(1), Flags);
2551     }
2552   }
2553
2554   // Otherwise unroll into some nasty scalar code and rebuild the vector.
2555   SmallVector<SDValue, 16> Ops(WidenNumElts);
2556   EVT EltVT = WidenVT.getVectorElementType();
2557   unsigned MinElts = std::min(InVTNumElts, WidenNumElts);
2558   unsigned i;
2559   for (i=0; i < MinElts; ++i) {
2560     SDValue Val = DAG.getNode(
2561         ISD::EXTRACT_VECTOR_ELT, DL, InEltVT, InOp,
2562         DAG.getConstant(i, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
2563     if (N->getNumOperands() == 1)
2564       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val);
2565     else
2566       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val, N->getOperand(1), Flags);
2567   }
2568
2569   SDValue UndefVal = DAG.getUNDEF(EltVT);
2570   for (; i < WidenNumElts; ++i)
2571     Ops[i] = UndefVal;
2572
2573   return DAG.getBuildVector(WidenVT, DL, Ops);
2574 }
2575
2576 SDValue DAGTypeLegalizer::WidenVecRes_EXTEND_VECTOR_INREG(SDNode *N) {
2577   unsigned Opcode = N->getOpcode();
2578   SDValue InOp = N->getOperand(0);
2579   SDLoc DL(N);
2580
2581   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2582   EVT WidenSVT = WidenVT.getVectorElementType();
2583   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2584
2585   EVT InVT = InOp.getValueType();
2586   EVT InSVT = InVT.getVectorElementType();
2587   unsigned InVTNumElts = InVT.getVectorNumElements();
2588
2589   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
2590     InOp = GetWidenedVector(InOp);
2591     InVT = InOp.getValueType();
2592     if (InVT.getSizeInBits() == WidenVT.getSizeInBits()) {
2593       switch (Opcode) {
2594       case ISD::ANY_EXTEND_VECTOR_INREG:
2595         return DAG.getAnyExtendVectorInReg(InOp, DL, WidenVT);
2596       case ISD::SIGN_EXTEND_VECTOR_INREG:
2597         return DAG.getSignExtendVectorInReg(InOp, DL, WidenVT);
2598       case ISD::ZERO_EXTEND_VECTOR_INREG:
2599         return DAG.getZeroExtendVectorInReg(InOp, DL, WidenVT);
2600       }
2601     }
2602   }
2603
2604   // Unroll, extend the scalars and rebuild the vector.
2605   SmallVector<SDValue, 16> Ops;
2606   for (unsigned i = 0, e = std::min(InVTNumElts, WidenNumElts); i != e; ++i) {
2607     SDValue Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, InSVT, InOp,
2608       DAG.getConstant(i, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
2609     switch (Opcode) {
2610     case ISD::ANY_EXTEND_VECTOR_INREG:
2611       Val = DAG.getNode(ISD::ANY_EXTEND, DL, WidenSVT, Val);
2612       break;
2613     case ISD::SIGN_EXTEND_VECTOR_INREG:
2614       Val = DAG.getNode(ISD::SIGN_EXTEND, DL, WidenSVT, Val);
2615       break;
2616     case ISD::ZERO_EXTEND_VECTOR_INREG:
2617       Val = DAG.getNode(ISD::ZERO_EXTEND, DL, WidenSVT, Val);
2618       break;
2619     default:
2620       llvm_unreachable("A *_EXTEND_VECTOR_INREG node was expected");
2621     }
2622     Ops.push_back(Val);
2623   }
2624
2625   while (Ops.size() != WidenNumElts)
2626     Ops.push_back(DAG.getUNDEF(WidenSVT));
2627
2628   return DAG.getBuildVector(WidenVT, DL, Ops);
2629 }
2630
2631 SDValue DAGTypeLegalizer::WidenVecRes_FCOPYSIGN(SDNode *N) {
2632   // If this is an FCOPYSIGN with same input types, we can treat it as a
2633   // normal (can trap) binary op.
2634   if (N->getOperand(0).getValueType() == N->getOperand(1).getValueType())
2635     return WidenVecRes_BinaryCanTrap(N);
2636
2637   // If the types are different, fall back to unrolling.
2638   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2639   return DAG.UnrollVectorOp(N, WidenVT.getVectorNumElements());
2640 }
2641
2642 SDValue DAGTypeLegalizer::WidenVecRes_POWI(SDNode *N) {
2643   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2644   SDValue InOp = GetWidenedVector(N->getOperand(0));
2645   SDValue ShOp = N->getOperand(1);
2646   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
2647 }
2648
2649 SDValue DAGTypeLegalizer::WidenVecRes_Shift(SDNode *N) {
2650   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2651   SDValue InOp = GetWidenedVector(N->getOperand(0));
2652   SDValue ShOp = N->getOperand(1);
2653
2654   EVT ShVT = ShOp.getValueType();
2655   if (getTypeAction(ShVT) == TargetLowering::TypeWidenVector) {
2656     ShOp = GetWidenedVector(ShOp);
2657     ShVT = ShOp.getValueType();
2658   }
2659   EVT ShWidenVT = EVT::getVectorVT(*DAG.getContext(),
2660                                    ShVT.getVectorElementType(),
2661                                    WidenVT.getVectorNumElements());
2662   if (ShVT != ShWidenVT)
2663     ShOp = ModifyToType(ShOp, ShWidenVT);
2664
2665   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
2666 }
2667
2668 SDValue DAGTypeLegalizer::WidenVecRes_Unary(SDNode *N) {
2669   // Unary op widening.
2670   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2671   SDValue InOp = GetWidenedVector(N->getOperand(0));
2672   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp);
2673 }
2674
2675 SDValue DAGTypeLegalizer::WidenVecRes_InregOp(SDNode *N) {
2676   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2677   EVT ExtVT = EVT::getVectorVT(*DAG.getContext(),
2678                                cast<VTSDNode>(N->getOperand(1))->getVT()
2679                                  .getVectorElementType(),
2680                                WidenVT.getVectorNumElements());
2681   SDValue WidenLHS = GetWidenedVector(N->getOperand(0));
2682   return DAG.getNode(N->getOpcode(), SDLoc(N),
2683                      WidenVT, WidenLHS, DAG.getValueType(ExtVT));
2684 }
2685
2686 SDValue DAGTypeLegalizer::WidenVecRes_MERGE_VALUES(SDNode *N, unsigned ResNo) {
2687   SDValue WidenVec = DisintegrateMERGE_VALUES(N, ResNo);
2688   return GetWidenedVector(WidenVec);
2689 }
2690
2691 SDValue DAGTypeLegalizer::WidenVecRes_BITCAST(SDNode *N) {
2692   SDValue InOp = N->getOperand(0);
2693   EVT InVT = InOp.getValueType();
2694   EVT VT = N->getValueType(0);
2695   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2696   SDLoc dl(N);
2697
2698   switch (getTypeAction(InVT)) {
2699   case TargetLowering::TypeLegal:
2700     break;
2701   case TargetLowering::TypePromoteInteger:
2702     // If the incoming type is a vector that is being promoted, then
2703     // we know that the elements are arranged differently and that we
2704     // must perform the conversion using a stack slot.
2705     if (InVT.isVector())
2706       break;
2707
2708     // If the InOp is promoted to the same size, convert it.  Otherwise,
2709     // fall out of the switch and widen the promoted input.
2710     InOp = GetPromotedInteger(InOp);
2711     InVT = InOp.getValueType();
2712     if (WidenVT.bitsEq(InVT))
2713       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
2714     break;
2715   case TargetLowering::TypeSoftenFloat:
2716   case TargetLowering::TypePromoteFloat:
2717   case TargetLowering::TypeExpandInteger:
2718   case TargetLowering::TypeExpandFloat:
2719   case TargetLowering::TypeScalarizeVector:
2720   case TargetLowering::TypeSplitVector:
2721     break;
2722   case TargetLowering::TypeWidenVector:
2723     // If the InOp is widened to the same size, convert it.  Otherwise, fall
2724     // out of the switch and widen the widened input.
2725     InOp = GetWidenedVector(InOp);
2726     InVT = InOp.getValueType();
2727     if (WidenVT.bitsEq(InVT))
2728       // The input widens to the same size. Convert to the widen value.
2729       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
2730     break;
2731   }
2732
2733   unsigned WidenSize = WidenVT.getSizeInBits();
2734   unsigned InSize = InVT.getSizeInBits();
2735   // x86mmx is not an acceptable vector element type, so don't try.
2736   if (WidenSize % InSize == 0 && InVT != MVT::x86mmx) {
2737     // Determine new input vector type.  The new input vector type will use
2738     // the same element type (if its a vector) or use the input type as a
2739     // vector.  It is the same size as the type to widen to.
2740     EVT NewInVT;
2741     unsigned NewNumElts = WidenSize / InSize;
2742     if (InVT.isVector()) {
2743       EVT InEltVT = InVT.getVectorElementType();
2744       NewInVT = EVT::getVectorVT(*DAG.getContext(), InEltVT,
2745                                  WidenSize / InEltVT.getSizeInBits());
2746     } else {
2747       NewInVT = EVT::getVectorVT(*DAG.getContext(), InVT, NewNumElts);
2748     }
2749
2750     if (TLI.isTypeLegal(NewInVT)) {
2751       // Because the result and the input are different vector types, widening
2752       // the result could create a legal type but widening the input might make
2753       // it an illegal type that might lead to repeatedly splitting the input
2754       // and then widening it. To avoid this, we widen the input only if
2755       // it results in a legal type.
2756       SmallVector<SDValue, 16> Ops(NewNumElts);
2757       SDValue UndefVal = DAG.getUNDEF(InVT);
2758       Ops[0] = InOp;
2759       for (unsigned i = 1; i < NewNumElts; ++i)
2760         Ops[i] = UndefVal;
2761
2762       SDValue NewVec;
2763       if (InVT.isVector())
2764         NewVec = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewInVT, Ops);
2765       else
2766         NewVec = DAG.getBuildVector(NewInVT, dl, Ops);
2767       return DAG.getNode(ISD::BITCAST, dl, WidenVT, NewVec);
2768     }
2769   }
2770
2771   return CreateStackStoreLoad(InOp, WidenVT);
2772 }
2773
2774 SDValue DAGTypeLegalizer::WidenVecRes_BUILD_VECTOR(SDNode *N) {
2775   SDLoc dl(N);
2776   // Build a vector with undefined for the new nodes.
2777   EVT VT = N->getValueType(0);
2778
2779   // Integer BUILD_VECTOR operands may be larger than the node's vector element
2780   // type. The UNDEFs need to have the same type as the existing operands.
2781   EVT EltVT = N->getOperand(0).getValueType();
2782   unsigned NumElts = VT.getVectorNumElements();
2783
2784   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2785   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2786
2787   SmallVector<SDValue, 16> NewOps(N->op_begin(), N->op_end());
2788   assert(WidenNumElts >= NumElts && "Shrinking vector instead of widening!");
2789   NewOps.append(WidenNumElts - NumElts, DAG.getUNDEF(EltVT));
2790
2791   return DAG.getBuildVector(WidenVT, dl, NewOps);
2792 }
2793
2794 SDValue DAGTypeLegalizer::WidenVecRes_CONCAT_VECTORS(SDNode *N) {
2795   EVT InVT = N->getOperand(0).getValueType();
2796   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2797   SDLoc dl(N);
2798   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2799   unsigned NumInElts = InVT.getVectorNumElements();
2800   unsigned NumOperands = N->getNumOperands();
2801
2802   bool InputWidened = false; // Indicates we need to widen the input.
2803   if (getTypeAction(InVT) != TargetLowering::TypeWidenVector) {
2804     if (WidenVT.getVectorNumElements() % InVT.getVectorNumElements() == 0) {
2805       // Add undef vectors to widen to correct length.
2806       unsigned NumConcat = WidenVT.getVectorNumElements() /
2807                            InVT.getVectorNumElements();
2808       SDValue UndefVal = DAG.getUNDEF(InVT);
2809       SmallVector<SDValue, 16> Ops(NumConcat);
2810       for (unsigned i=0; i < NumOperands; ++i)
2811         Ops[i] = N->getOperand(i);
2812       for (unsigned i = NumOperands; i != NumConcat; ++i)
2813         Ops[i] = UndefVal;
2814       return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, Ops);
2815     }
2816   } else {
2817     InputWidened = true;
2818     if (WidenVT == TLI.getTypeToTransformTo(*DAG.getContext(), InVT)) {
2819       // The inputs and the result are widen to the same value.
2820       unsigned i;
2821       for (i=1; i < NumOperands; ++i)
2822         if (!N->getOperand(i).isUndef())
2823           break;
2824
2825       if (i == NumOperands)
2826         // Everything but the first operand is an UNDEF so just return the
2827         // widened first operand.
2828         return GetWidenedVector(N->getOperand(0));
2829
2830       if (NumOperands == 2) {
2831         // Replace concat of two operands with a shuffle.
2832         SmallVector<int, 16> MaskOps(WidenNumElts, -1);
2833         for (unsigned i = 0; i < NumInElts; ++i) {
2834           MaskOps[i] = i;
2835           MaskOps[i + NumInElts] = i + WidenNumElts;
2836         }
2837         return DAG.getVectorShuffle(WidenVT, dl,
2838                                     GetWidenedVector(N->getOperand(0)),
2839                                     GetWidenedVector(N->getOperand(1)),
2840                                     MaskOps);
2841       }
2842     }
2843   }
2844
2845   // Fall back to use extracts and build vector.
2846   EVT EltVT = WidenVT.getVectorElementType();
2847   SmallVector<SDValue, 16> Ops(WidenNumElts);
2848   unsigned Idx = 0;
2849   for (unsigned i=0; i < NumOperands; ++i) {
2850     SDValue InOp = N->getOperand(i);
2851     if (InputWidened)
2852       InOp = GetWidenedVector(InOp);
2853     for (unsigned j=0; j < NumInElts; ++j)
2854       Ops[Idx++] = DAG.getNode(
2855           ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2856           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2857   }
2858   SDValue UndefVal = DAG.getUNDEF(EltVT);
2859   for (; Idx < WidenNumElts; ++Idx)
2860     Ops[Idx] = UndefVal;
2861   return DAG.getBuildVector(WidenVT, dl, Ops);
2862 }
2863
2864 SDValue DAGTypeLegalizer::WidenVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
2865   EVT      VT = N->getValueType(0);
2866   EVT      WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2867   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2868   SDValue  InOp = N->getOperand(0);
2869   SDValue  Idx  = N->getOperand(1);
2870   SDLoc dl(N);
2871
2872   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2873     InOp = GetWidenedVector(InOp);
2874
2875   EVT InVT = InOp.getValueType();
2876
2877   // Check if we can just return the input vector after widening.
2878   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
2879   if (IdxVal == 0 && InVT == WidenVT)
2880     return InOp;
2881
2882   // Check if we can extract from the vector.
2883   unsigned InNumElts = InVT.getVectorNumElements();
2884   if (IdxVal % WidenNumElts == 0 && IdxVal + WidenNumElts < InNumElts)
2885     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, WidenVT, InOp, Idx);
2886
2887   // We could try widening the input to the right length but for now, extract
2888   // the original elements, fill the rest with undefs and build a vector.
2889   SmallVector<SDValue, 16> Ops(WidenNumElts);
2890   EVT EltVT = VT.getVectorElementType();
2891   unsigned NumElts = VT.getVectorNumElements();
2892   unsigned i;
2893   for (i=0; i < NumElts; ++i)
2894     Ops[i] =
2895         DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2896                     DAG.getConstant(IdxVal + i, dl,
2897                                     TLI.getVectorIdxTy(DAG.getDataLayout())));
2898
2899   SDValue UndefVal = DAG.getUNDEF(EltVT);
2900   for (; i < WidenNumElts; ++i)
2901     Ops[i] = UndefVal;
2902   return DAG.getBuildVector(WidenVT, dl, Ops);
2903 }
2904
2905 SDValue DAGTypeLegalizer::WidenVecRes_INSERT_VECTOR_ELT(SDNode *N) {
2906   SDValue InOp = GetWidenedVector(N->getOperand(0));
2907   return DAG.getNode(ISD::INSERT_VECTOR_ELT, SDLoc(N),
2908                      InOp.getValueType(), InOp,
2909                      N->getOperand(1), N->getOperand(2));
2910 }
2911
2912 SDValue DAGTypeLegalizer::WidenVecRes_LOAD(SDNode *N) {
2913   LoadSDNode *LD = cast<LoadSDNode>(N);
2914   ISD::LoadExtType ExtType = LD->getExtensionType();
2915
2916   SDValue Result;
2917   SmallVector<SDValue, 16> LdChain;  // Chain for the series of load
2918   if (ExtType != ISD::NON_EXTLOAD)
2919     Result = GenWidenVectorExtLoads(LdChain, LD, ExtType);
2920   else
2921     Result = GenWidenVectorLoads(LdChain, LD);
2922
2923   // If we generate a single load, we can use that for the chain.  Otherwise,
2924   // build a factor node to remember the multiple loads are independent and
2925   // chain to that.
2926   SDValue NewChain;
2927   if (LdChain.size() == 1)
2928     NewChain = LdChain[0];
2929   else
2930     NewChain = DAG.getNode(ISD::TokenFactor, SDLoc(LD), MVT::Other, LdChain);
2931
2932   // Modified the chain - switch anything that used the old chain to use
2933   // the new one.
2934   ReplaceValueWith(SDValue(N, 1), NewChain);
2935
2936   return Result;
2937 }
2938
2939 SDValue DAGTypeLegalizer::WidenVecRes_MLOAD(MaskedLoadSDNode *N) {
2940
2941   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),N->getValueType(0));
2942   SDValue Mask = N->getMask();
2943   EVT MaskVT = Mask.getValueType();
2944   SDValue Src0 = GetWidenedVector(N->getSrc0());
2945   ISD::LoadExtType ExtType = N->getExtensionType();
2946   SDLoc dl(N);
2947
2948   // The mask should be widened as well
2949   EVT WideMaskVT = EVT::getVectorVT(*DAG.getContext(),
2950                                     MaskVT.getVectorElementType(),
2951                                     WidenVT.getVectorNumElements());
2952   Mask = ModifyToType(Mask, WideMaskVT, true);
2953
2954   SDValue Res = DAG.getMaskedLoad(WidenVT, dl, N->getChain(), N->getBasePtr(),
2955                                   Mask, Src0, N->getMemoryVT(),
2956                                   N->getMemOperand(), ExtType,
2957                                         N->isExpandingLoad());
2958   // Legalize the chain result - switch anything that used the old chain to
2959   // use the new one.
2960   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
2961   return Res;
2962 }
2963
2964 SDValue DAGTypeLegalizer::WidenVecRes_MGATHER(MaskedGatherSDNode *N) {
2965
2966   EVT WideVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2967   SDValue Mask = N->getMask();
2968   EVT MaskVT = Mask.getValueType();
2969   SDValue Src0 = GetWidenedVector(N->getValue());
2970   SDValue Scale = N->getScale();
2971   unsigned NumElts = WideVT.getVectorNumElements();
2972   SDLoc dl(N);
2973
2974   // The mask should be widened as well
2975   EVT WideMaskVT = EVT::getVectorVT(*DAG.getContext(),
2976                                     MaskVT.getVectorElementType(),
2977                                     WideVT.getVectorNumElements());
2978   Mask = ModifyToType(Mask, WideMaskVT, true);
2979
2980   // Widen the Index operand
2981   SDValue Index = N->getIndex();
2982   EVT WideIndexVT = EVT::getVectorVT(*DAG.getContext(),
2983                                      Index.getValueType().getScalarType(),
2984                                      NumElts);
2985   Index = ModifyToType(Index, WideIndexVT);
2986   SDValue Ops[] = { N->getChain(), Src0, Mask, N->getBasePtr(), Index, Scale };
2987   SDValue Res = DAG.getMaskedGather(DAG.getVTList(WideVT, MVT::Other),
2988                                     N->getMemoryVT(), dl, Ops,
2989                                     N->getMemOperand());
2990
2991   // Legalize the chain result - switch anything that used the old chain to
2992   // use the new one.
2993   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
2994   return Res;
2995 }
2996
2997 SDValue DAGTypeLegalizer::WidenVecRes_SCALAR_TO_VECTOR(SDNode *N) {
2998   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2999   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N),
3000                      WidenVT, N->getOperand(0));
3001 }
3002
3003 // Return true if this is a node that could have two SETCCs as operands.
3004 static inline bool isLogicalMaskOp(unsigned Opcode) {
3005   switch (Opcode) {
3006   case ISD::AND:
3007   case ISD::OR:
3008   case ISD::XOR:
3009     return true;
3010   }
3011   return false;
3012 }
3013
3014 // This is used just for the assert in convertMask(). Check that this either
3015 // a SETCC or a previously handled SETCC by convertMask().
3016 #ifndef NDEBUG
3017 static inline bool isSETCCorConvertedSETCC(SDValue N) {
3018   if (N.getOpcode() == ISD::EXTRACT_SUBVECTOR)
3019     N = N.getOperand(0);
3020   else if (N.getOpcode() == ISD::CONCAT_VECTORS) {
3021     for (unsigned i = 1; i < N->getNumOperands(); ++i)
3022       if (!N->getOperand(i)->isUndef())
3023         return false;
3024     N = N.getOperand(0);
3025   }
3026
3027   if (N.getOpcode() == ISD::TRUNCATE)
3028     N = N.getOperand(0);
3029   else if (N.getOpcode() == ISD::SIGN_EXTEND)
3030     N = N.getOperand(0);
3031
3032   if (isLogicalMaskOp(N.getOpcode()))
3033     return isSETCCorConvertedSETCC(N.getOperand(0)) &&
3034            isSETCCorConvertedSETCC(N.getOperand(1));
3035
3036   return (N.getOpcode() == ISD::SETCC ||
3037           ISD::isBuildVectorOfConstantSDNodes(N.getNode()));
3038 }
3039 #endif
3040
3041 // Return a mask of vector type MaskVT to replace InMask. Also adjust MaskVT
3042 // to ToMaskVT if needed with vector extension or truncation.
3043 SDValue DAGTypeLegalizer::convertMask(SDValue InMask, EVT MaskVT,
3044                                       EVT ToMaskVT) {
3045   // Currently a SETCC or a AND/OR/XOR with two SETCCs are handled.
3046   // FIXME: This code seems to be too restrictive, we might consider
3047   // generalizing it or dropping it.
3048   assert(isSETCCorConvertedSETCC(InMask) && "Unexpected mask argument.");
3049
3050   // Make a new Mask node, with a legal result VT.
3051   SmallVector<SDValue, 4> Ops;
3052   for (unsigned i = 0, e = InMask->getNumOperands(); i < e; ++i)
3053     Ops.push_back(InMask->getOperand(i));
3054   SDValue Mask = DAG.getNode(InMask->getOpcode(), SDLoc(InMask), MaskVT, Ops);
3055
3056   // If MaskVT has smaller or bigger elements than ToMaskVT, a vector sign
3057   // extend or truncate is needed.
3058   LLVMContext &Ctx = *DAG.getContext();
3059   unsigned MaskScalarBits = MaskVT.getScalarSizeInBits();
3060   unsigned ToMaskScalBits = ToMaskVT.getScalarSizeInBits();
3061   if (MaskScalarBits < ToMaskScalBits) {
3062     EVT ExtVT = EVT::getVectorVT(Ctx, ToMaskVT.getVectorElementType(),
3063                                  MaskVT.getVectorNumElements());
3064     Mask = DAG.getNode(ISD::SIGN_EXTEND, SDLoc(Mask), ExtVT, Mask);
3065   } else if (MaskScalarBits > ToMaskScalBits) {
3066     EVT TruncVT = EVT::getVectorVT(Ctx, ToMaskVT.getVectorElementType(),
3067                                    MaskVT.getVectorNumElements());
3068     Mask = DAG.getNode(ISD::TRUNCATE, SDLoc(Mask), TruncVT, Mask);
3069   }
3070
3071   assert(Mask->getValueType(0).getScalarSizeInBits() ==
3072              ToMaskVT.getScalarSizeInBits() &&
3073          "Mask should have the right element size by now.");
3074
3075   // Adjust Mask to the right number of elements.
3076   unsigned CurrMaskNumEls = Mask->getValueType(0).getVectorNumElements();
3077   if (CurrMaskNumEls > ToMaskVT.getVectorNumElements()) {
3078     MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
3079     SDValue ZeroIdx = DAG.getConstant(0, SDLoc(Mask), IdxTy);
3080     Mask = DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(Mask), ToMaskVT, Mask,
3081                        ZeroIdx);
3082   } else if (CurrMaskNumEls < ToMaskVT.getVectorNumElements()) {
3083     unsigned NumSubVecs = (ToMaskVT.getVectorNumElements() / CurrMaskNumEls);
3084     EVT SubVT = Mask->getValueType(0);
3085     SmallVector<SDValue, 16> SubOps(NumSubVecs, DAG.getUNDEF(SubVT));
3086     SubOps[0] = Mask;
3087     Mask = DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(Mask), ToMaskVT, SubOps);
3088   }
3089
3090   assert((Mask->getValueType(0) == ToMaskVT) &&
3091          "A mask of ToMaskVT should have been produced by now.");
3092
3093   return Mask;
3094 }
3095
3096 // Get the target mask VT, and widen if needed.
3097 EVT DAGTypeLegalizer::getSETCCWidenedResultTy(SDValue SetCC) {
3098   assert(SetCC->getOpcode() == ISD::SETCC);
3099   LLVMContext &Ctx = *DAG.getContext();
3100   EVT MaskVT = getSetCCResultType(SetCC->getOperand(0).getValueType());
3101   if (getTypeAction(MaskVT) == TargetLowering::TypeWidenVector)
3102     MaskVT = TLI.getTypeToTransformTo(Ctx, MaskVT);
3103   return MaskVT;
3104 }
3105
3106 // This method tries to handle VSELECT and its mask by legalizing operands
3107 // (which may require widening) and if needed adjusting the mask vector type
3108 // to match that of the VSELECT. Without it, many cases end up with
3109 // scalarization of the SETCC, with many unnecessary instructions.
3110 SDValue DAGTypeLegalizer::WidenVSELECTAndMask(SDNode *N) {
3111   LLVMContext &Ctx = *DAG.getContext();
3112   SDValue Cond = N->getOperand(0);
3113
3114   if (N->getOpcode() != ISD::VSELECT)
3115     return SDValue();
3116
3117   if (Cond->getOpcode() != ISD::SETCC && !isLogicalMaskOp(Cond->getOpcode()))
3118     return SDValue();
3119
3120   // If this is a splitted VSELECT that was previously already handled, do
3121   // nothing.
3122   EVT CondVT = Cond->getValueType(0);
3123   if (CondVT.getScalarSizeInBits() != 1)
3124     return SDValue();
3125
3126   EVT VSelVT = N->getValueType(0);
3127   // Only handle vector types which are a power of 2.
3128   if (!isPowerOf2_64(VSelVT.getSizeInBits()))
3129     return SDValue();
3130
3131   // Don't touch if this will be scalarized.
3132   EVT FinalVT = VSelVT;
3133   while (getTypeAction(FinalVT) == TargetLowering::TypeSplitVector)
3134     FinalVT = FinalVT.getHalfNumVectorElementsVT(Ctx);
3135
3136   if (FinalVT.getVectorNumElements() == 1)
3137     return SDValue();
3138
3139   // If there is support for an i1 vector mask, don't touch.
3140   if (Cond.getOpcode() == ISD::SETCC) {
3141     EVT SetCCOpVT = Cond->getOperand(0).getValueType();
3142     while (TLI.getTypeAction(Ctx, SetCCOpVT) != TargetLowering::TypeLegal)
3143       SetCCOpVT = TLI.getTypeToTransformTo(Ctx, SetCCOpVT);
3144     EVT SetCCResVT = getSetCCResultType(SetCCOpVT);
3145     if (SetCCResVT.getScalarSizeInBits() == 1)
3146       return SDValue();
3147   } else if (CondVT.getScalarType() == MVT::i1) {
3148     // If there is support for an i1 vector mask (or only scalar i1 conditions),
3149     // don't touch.
3150     while (TLI.getTypeAction(Ctx, CondVT) != TargetLowering::TypeLegal)
3151       CondVT = TLI.getTypeToTransformTo(Ctx, CondVT);
3152
3153     if (CondVT.getScalarType() == MVT::i1)
3154       return SDValue();
3155   }
3156
3157   // Get the VT and operands for VSELECT, and widen if needed.
3158   SDValue VSelOp1 = N->getOperand(1);
3159   SDValue VSelOp2 = N->getOperand(2);
3160   if (getTypeAction(VSelVT) == TargetLowering::TypeWidenVector) {
3161     VSelVT = TLI.getTypeToTransformTo(Ctx, VSelVT);
3162     VSelOp1 = GetWidenedVector(VSelOp1);
3163     VSelOp2 = GetWidenedVector(VSelOp2);
3164   }
3165
3166   // The mask of the VSELECT should have integer elements.
3167   EVT ToMaskVT = VSelVT;
3168   if (!ToMaskVT.getScalarType().isInteger())
3169     ToMaskVT = ToMaskVT.changeVectorElementTypeToInteger();
3170
3171   SDValue Mask;
3172   if (Cond->getOpcode() == ISD::SETCC) {
3173     EVT MaskVT = getSETCCWidenedResultTy(Cond);
3174     Mask = convertMask(Cond, MaskVT, ToMaskVT);
3175   } else if (isLogicalMaskOp(Cond->getOpcode()) &&
3176              Cond->getOperand(0).getOpcode() == ISD::SETCC &&
3177              Cond->getOperand(1).getOpcode() == ISD::SETCC) {
3178     // Cond is (AND/OR/XOR (SETCC, SETCC))
3179     SDValue SETCC0 = Cond->getOperand(0);
3180     SDValue SETCC1 = Cond->getOperand(1);
3181     EVT VT0 = getSETCCWidenedResultTy(SETCC0);
3182     EVT VT1 = getSETCCWidenedResultTy(SETCC1);
3183     unsigned ScalarBits0 = VT0.getScalarSizeInBits();
3184     unsigned ScalarBits1 = VT1.getScalarSizeInBits();
3185     unsigned ScalarBits_ToMask = ToMaskVT.getScalarSizeInBits();
3186     EVT MaskVT;
3187     // If the two SETCCs have different VTs, either extend/truncate one of
3188     // them to the other "towards" ToMaskVT, or truncate one and extend the
3189     // other to ToMaskVT.
3190     if (ScalarBits0 != ScalarBits1) {
3191       EVT NarrowVT = ((ScalarBits0 < ScalarBits1) ? VT0 : VT1);
3192       EVT WideVT = ((NarrowVT == VT0) ? VT1 : VT0);
3193       if (ScalarBits_ToMask >= WideVT.getScalarSizeInBits())
3194         MaskVT = WideVT;
3195       else if (ScalarBits_ToMask <= NarrowVT.getScalarSizeInBits())
3196         MaskVT = NarrowVT;
3197       else
3198         MaskVT = ToMaskVT;
3199     } else
3200       // If the two SETCCs have the same VT, don't change it.
3201       MaskVT = VT0;
3202
3203     // Make new SETCCs and logical nodes.
3204     SETCC0 = convertMask(SETCC0, VT0, MaskVT);
3205     SETCC1 = convertMask(SETCC1, VT1, MaskVT);
3206     Cond = DAG.getNode(Cond->getOpcode(), SDLoc(Cond), MaskVT, SETCC0, SETCC1);
3207
3208     // Convert the logical op for VSELECT if needed.
3209     Mask = convertMask(Cond, MaskVT, ToMaskVT);
3210   } else
3211     return SDValue();
3212
3213   return DAG.getNode(ISD::VSELECT, SDLoc(N), VSelVT, Mask, VSelOp1, VSelOp2);
3214 }
3215
3216 SDValue DAGTypeLegalizer::WidenVecRes_SELECT(SDNode *N) {
3217   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3218   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3219
3220   SDValue Cond1 = N->getOperand(0);
3221   EVT CondVT = Cond1.getValueType();
3222   if (CondVT.isVector()) {
3223     if (SDValue Res = WidenVSELECTAndMask(N))
3224       return Res;
3225
3226     EVT CondEltVT = CondVT.getVectorElementType();
3227     EVT CondWidenVT =  EVT::getVectorVT(*DAG.getContext(),
3228                                         CondEltVT, WidenNumElts);
3229     if (getTypeAction(CondVT) == TargetLowering::TypeWidenVector)
3230       Cond1 = GetWidenedVector(Cond1);
3231
3232     // If we have to split the condition there is no point in widening the
3233     // select. This would result in an cycle of widening the select ->
3234     // widening the condition operand -> splitting the condition operand ->
3235     // splitting the select -> widening the select. Instead split this select
3236     // further and widen the resulting type.
3237     if (getTypeAction(CondVT) == TargetLowering::TypeSplitVector) {
3238       SDValue SplitSelect = SplitVecOp_VSELECT(N, 0);
3239       SDValue Res = ModifyToType(SplitSelect, WidenVT);
3240       return Res;
3241     }
3242
3243     if (Cond1.getValueType() != CondWidenVT)
3244       Cond1 = ModifyToType(Cond1, CondWidenVT);
3245   }
3246
3247   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
3248   SDValue InOp2 = GetWidenedVector(N->getOperand(2));
3249   assert(InOp1.getValueType() == WidenVT && InOp2.getValueType() == WidenVT);
3250   return DAG.getNode(N->getOpcode(), SDLoc(N),
3251                      WidenVT, Cond1, InOp1, InOp2);
3252 }
3253
3254 SDValue DAGTypeLegalizer::WidenVecRes_SELECT_CC(SDNode *N) {
3255   SDValue InOp1 = GetWidenedVector(N->getOperand(2));
3256   SDValue InOp2 = GetWidenedVector(N->getOperand(3));
3257   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
3258                      InOp1.getValueType(), N->getOperand(0),
3259                      N->getOperand(1), InOp1, InOp2, N->getOperand(4));
3260 }
3261
3262 SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) {
3263  EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3264  return DAG.getUNDEF(WidenVT);
3265 }
3266
3267 SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N) {
3268   EVT VT = N->getValueType(0);
3269   SDLoc dl(N);
3270
3271   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3272   unsigned NumElts = VT.getVectorNumElements();
3273   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3274
3275   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
3276   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3277
3278   // Adjust mask based on new input vector length.
3279   SmallVector<int, 16> NewMask;
3280   for (unsigned i = 0; i != NumElts; ++i) {
3281     int Idx = N->getMaskElt(i);
3282     if (Idx < (int)NumElts)
3283       NewMask.push_back(Idx);
3284     else
3285       NewMask.push_back(Idx - NumElts + WidenNumElts);
3286   }
3287   for (unsigned i = NumElts; i != WidenNumElts; ++i)
3288     NewMask.push_back(-1);
3289   return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, NewMask);
3290 }
3291
3292 SDValue DAGTypeLegalizer::WidenVecRes_SETCC(SDNode *N) {
3293   assert(N->getValueType(0).isVector() &&
3294          N->getOperand(0).getValueType().isVector() &&
3295          "Operands must be vectors");
3296   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3297   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3298
3299   SDValue InOp1 = N->getOperand(0);
3300   EVT InVT = InOp1.getValueType();
3301   assert(InVT.isVector() && "can not widen non-vector type");
3302   EVT WidenInVT = EVT::getVectorVT(*DAG.getContext(),
3303                                    InVT.getVectorElementType(), WidenNumElts);
3304
3305   // The input and output types often differ here, and it could be that while
3306   // we'd prefer to widen the result type, the input operands have been split.
3307   // In this case, we also need to split the result of this node as well.
3308   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector) {
3309     SDValue SplitVSetCC = SplitVecOp_VSETCC(N);
3310     SDValue Res = ModifyToType(SplitVSetCC, WidenVT);
3311     return Res;
3312   }
3313
3314   InOp1 = GetWidenedVector(InOp1);
3315   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3316
3317   // Assume that the input and output will be widen appropriately.  If not,
3318   // we will have to unroll it at some point.
3319   assert(InOp1.getValueType() == WidenInVT &&
3320          InOp2.getValueType() == WidenInVT &&
3321          "Input not widened to expected type!");
3322   (void)WidenInVT;
3323   return DAG.getNode(ISD::SETCC, SDLoc(N),
3324                      WidenVT, InOp1, InOp2, N->getOperand(2));
3325 }
3326
3327
3328 //===----------------------------------------------------------------------===//
3329 // Widen Vector Operand
3330 //===----------------------------------------------------------------------===//
3331 bool DAGTypeLegalizer::WidenVectorOperand(SDNode *N, unsigned OpNo) {
3332   DEBUG(dbgs() << "Widen node operand " << OpNo << ": ";
3333         N->dump(&DAG);
3334         dbgs() << "\n");
3335   SDValue Res = SDValue();
3336
3337   // See if the target wants to custom widen this node.
3338   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
3339     return false;
3340
3341   switch (N->getOpcode()) {
3342   default:
3343 #ifndef NDEBUG
3344     dbgs() << "WidenVectorOperand op #" << OpNo << ": ";
3345     N->dump(&DAG);
3346     dbgs() << "\n";
3347 #endif
3348     llvm_unreachable("Do not know how to widen this operator's operand!");
3349
3350   case ISD::BITCAST:            Res = WidenVecOp_BITCAST(N); break;
3351   case ISD::CONCAT_VECTORS:     Res = WidenVecOp_CONCAT_VECTORS(N); break;
3352   case ISD::EXTRACT_SUBVECTOR:  Res = WidenVecOp_EXTRACT_SUBVECTOR(N); break;
3353   case ISD::EXTRACT_VECTOR_ELT: Res = WidenVecOp_EXTRACT_VECTOR_ELT(N); break;
3354   case ISD::STORE:              Res = WidenVecOp_STORE(N); break;
3355   case ISD::MSTORE:             Res = WidenVecOp_MSTORE(N, OpNo); break;
3356   case ISD::MSCATTER:           Res = WidenVecOp_MSCATTER(N, OpNo); break;
3357   case ISD::SETCC:              Res = WidenVecOp_SETCC(N); break;
3358   case ISD::FCOPYSIGN:          Res = WidenVecOp_FCOPYSIGN(N); break;
3359
3360   case ISD::ANY_EXTEND:
3361   case ISD::SIGN_EXTEND:
3362   case ISD::ZERO_EXTEND:
3363     Res = WidenVecOp_EXTEND(N);
3364     break;
3365
3366   case ISD::FP_EXTEND:
3367   case ISD::FP_TO_SINT:
3368   case ISD::FP_TO_UINT:
3369   case ISD::SINT_TO_FP:
3370   case ISD::UINT_TO_FP:
3371   case ISD::TRUNCATE:
3372     Res = WidenVecOp_Convert(N);
3373     break;
3374   }
3375
3376   // If Res is null, the sub-method took care of registering the result.
3377   if (!Res.getNode()) return false;
3378
3379   // If the result is N, the sub-method updated N in place.  Tell the legalizer
3380   // core about this.
3381   if (Res.getNode() == N)
3382     return true;
3383
3384
3385   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
3386          "Invalid operand expansion");
3387
3388   ReplaceValueWith(SDValue(N, 0), Res);
3389   return false;
3390 }
3391
3392 SDValue DAGTypeLegalizer::WidenVecOp_EXTEND(SDNode *N) {
3393   SDLoc DL(N);
3394   EVT VT = N->getValueType(0);
3395
3396   SDValue InOp = N->getOperand(0);
3397   assert(getTypeAction(InOp.getValueType()) ==
3398              TargetLowering::TypeWidenVector &&
3399          "Unexpected type action");
3400   InOp = GetWidenedVector(InOp);
3401   assert(VT.getVectorNumElements() <
3402              InOp.getValueType().getVectorNumElements() &&
3403          "Input wasn't widened!");
3404
3405   // We may need to further widen the operand until it has the same total
3406   // vector size as the result.
3407   EVT InVT = InOp.getValueType();
3408   if (InVT.getSizeInBits() != VT.getSizeInBits()) {
3409     EVT InEltVT = InVT.getVectorElementType();
3410     for (int i = MVT::FIRST_VECTOR_VALUETYPE, e = MVT::LAST_VECTOR_VALUETYPE; i < e; ++i) {
3411       EVT FixedVT = (MVT::SimpleValueType)i;
3412       EVT FixedEltVT = FixedVT.getVectorElementType();
3413       if (TLI.isTypeLegal(FixedVT) &&
3414           FixedVT.getSizeInBits() == VT.getSizeInBits() &&
3415           FixedEltVT == InEltVT) {
3416         assert(FixedVT.getVectorNumElements() >= VT.getVectorNumElements() &&
3417                "Not enough elements in the fixed type for the operand!");
3418         assert(FixedVT.getVectorNumElements() != InVT.getVectorNumElements() &&
3419                "We can't have the same type as we started with!");
3420         if (FixedVT.getVectorNumElements() > InVT.getVectorNumElements())
3421           InOp = DAG.getNode(
3422               ISD::INSERT_SUBVECTOR, DL, FixedVT, DAG.getUNDEF(FixedVT), InOp,
3423               DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
3424         else
3425           InOp = DAG.getNode(
3426               ISD::EXTRACT_SUBVECTOR, DL, FixedVT, InOp,
3427               DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
3428         break;
3429       }
3430     }
3431     InVT = InOp.getValueType();
3432     if (InVT.getSizeInBits() != VT.getSizeInBits())
3433       // We couldn't find a legal vector type that was a widening of the input
3434       // and could be extended in-register to the result type, so we have to
3435       // scalarize.
3436       return WidenVecOp_Convert(N);
3437   }
3438
3439   // Use special DAG nodes to represent the operation of extending the
3440   // low lanes.
3441   switch (N->getOpcode()) {
3442   default:
3443     llvm_unreachable("Extend legalization on extend operation!");
3444   case ISD::ANY_EXTEND:
3445     return DAG.getAnyExtendVectorInReg(InOp, DL, VT);
3446   case ISD::SIGN_EXTEND:
3447     return DAG.getSignExtendVectorInReg(InOp, DL, VT);
3448   case ISD::ZERO_EXTEND:
3449     return DAG.getZeroExtendVectorInReg(InOp, DL, VT);
3450   }
3451 }
3452
3453 SDValue DAGTypeLegalizer::WidenVecOp_FCOPYSIGN(SDNode *N) {
3454   // The result (and first input) is legal, but the second input is illegal.
3455   // We can't do much to fix that, so just unroll and let the extracts off of
3456   // the second input be widened as needed later.
3457   return DAG.UnrollVectorOp(N);
3458 }
3459
3460 SDValue DAGTypeLegalizer::WidenVecOp_Convert(SDNode *N) {
3461   // Since the result is legal and the input is illegal.
3462   EVT VT = N->getValueType(0);
3463   EVT EltVT = VT.getVectorElementType();
3464   SDLoc dl(N);
3465   unsigned NumElts = VT.getVectorNumElements();
3466   SDValue InOp = N->getOperand(0);
3467   assert(getTypeAction(InOp.getValueType()) ==
3468              TargetLowering::TypeWidenVector &&
3469          "Unexpected type action");
3470   InOp = GetWidenedVector(InOp);
3471   EVT InVT = InOp.getValueType();
3472   unsigned Opcode = N->getOpcode();
3473
3474   // See if a widened result type would be legal, if so widen the node.
3475   EVT WideVT = EVT::getVectorVT(*DAG.getContext(), EltVT,
3476                                 InVT.getVectorNumElements());
3477   if (TLI.isTypeLegal(WideVT)) {
3478     SDValue Res = DAG.getNode(Opcode, dl, WideVT, InOp);
3479     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, Res,
3480                        DAG.getIntPtrConstant(0, dl));
3481   }
3482
3483   EVT InEltVT = InVT.getVectorElementType();
3484
3485   // Unroll the convert into some scalar code and create a nasty build vector.
3486   SmallVector<SDValue, 16> Ops(NumElts);
3487   for (unsigned i=0; i < NumElts; ++i)
3488     Ops[i] = DAG.getNode(
3489         Opcode, dl, EltVT,
3490         DAG.getNode(
3491             ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
3492             DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout()))));
3493
3494   return DAG.getBuildVector(VT, dl, Ops);
3495 }
3496
3497 SDValue DAGTypeLegalizer::WidenVecOp_BITCAST(SDNode *N) {
3498   EVT VT = N->getValueType(0);
3499   SDValue InOp = GetWidenedVector(N->getOperand(0));
3500   EVT InWidenVT = InOp.getValueType();
3501   SDLoc dl(N);
3502
3503   // Check if we can convert between two legal vector types and extract.
3504   unsigned InWidenSize = InWidenVT.getSizeInBits();
3505   unsigned Size = VT.getSizeInBits();
3506   // x86mmx is not an acceptable vector element type, so don't try.
3507   if (InWidenSize % Size == 0 && !VT.isVector() && VT != MVT::x86mmx) {
3508     unsigned NewNumElts = InWidenSize / Size;
3509     EVT NewVT = EVT::getVectorVT(*DAG.getContext(), VT, NewNumElts);
3510     if (TLI.isTypeLegal(NewVT)) {
3511       SDValue BitOp = DAG.getNode(ISD::BITCAST, dl, NewVT, InOp);
3512       return DAG.getNode(
3513           ISD::EXTRACT_VECTOR_ELT, dl, VT, BitOp,
3514           DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3515     }
3516   }
3517
3518   return CreateStackStoreLoad(InOp, VT);
3519 }
3520
3521 SDValue DAGTypeLegalizer::WidenVecOp_CONCAT_VECTORS(SDNode *N) {
3522   // If the input vector is not legal, it is likely that we will not find a
3523   // legal vector of the same size. Replace the concatenate vector with a
3524   // nasty build vector.
3525   EVT VT = N->getValueType(0);
3526   EVT EltVT = VT.getVectorElementType();
3527   SDLoc dl(N);
3528   unsigned NumElts = VT.getVectorNumElements();
3529   SmallVector<SDValue, 16> Ops(NumElts);
3530
3531   EVT InVT = N->getOperand(0).getValueType();
3532   unsigned NumInElts = InVT.getVectorNumElements();
3533
3534   unsigned Idx = 0;
3535   unsigned NumOperands = N->getNumOperands();
3536   for (unsigned i=0; i < NumOperands; ++i) {
3537     SDValue InOp = N->getOperand(i);
3538     assert(getTypeAction(InOp.getValueType()) ==
3539                TargetLowering::TypeWidenVector &&
3540            "Unexpected type action");
3541     InOp = GetWidenedVector(InOp);
3542     for (unsigned j=0; j < NumInElts; ++j)
3543       Ops[Idx++] = DAG.getNode(
3544           ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
3545           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3546   }
3547   return DAG.getBuildVector(VT, dl, Ops);
3548 }
3549
3550 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
3551   SDValue InOp = GetWidenedVector(N->getOperand(0));
3552   return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(N),
3553                      N->getValueType(0), InOp, N->getOperand(1));
3554 }
3555
3556 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
3557   SDValue InOp = GetWidenedVector(N->getOperand(0));
3558   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
3559                      N->getValueType(0), InOp, N->getOperand(1));
3560 }
3561
3562 SDValue DAGTypeLegalizer::WidenVecOp_STORE(SDNode *N) {
3563   // We have to widen the value, but we want only to store the original
3564   // vector type.
3565   StoreSDNode *ST = cast<StoreSDNode>(N);
3566
3567   if (!ST->getMemoryVT().getScalarType().isByteSized())
3568     return TLI.scalarizeVectorStore(ST, DAG);
3569
3570   SmallVector<SDValue, 16> StChain;
3571   if (ST->isTruncatingStore())
3572     GenWidenVectorTruncStores(StChain, ST);
3573   else
3574     GenWidenVectorStores(StChain, ST);
3575
3576   if (StChain.size() == 1)
3577     return StChain[0];
3578   else
3579     return DAG.getNode(ISD::TokenFactor, SDLoc(ST), MVT::Other, StChain);
3580 }
3581
3582 SDValue DAGTypeLegalizer::WidenVecOp_MSTORE(SDNode *N, unsigned OpNo) {
3583   assert(OpNo == 3 && "Can widen only data operand of mstore");
3584   MaskedStoreSDNode *MST = cast<MaskedStoreSDNode>(N);
3585   SDValue Mask = MST->getMask();
3586   EVT MaskVT = Mask.getValueType();
3587   SDValue StVal = MST->getValue();
3588   // Widen the value
3589   SDValue WideVal = GetWidenedVector(StVal);
3590   SDLoc dl(N);
3591
3592   // The mask should be widened as well.
3593   EVT WideVT = WideVal.getValueType();
3594   EVT WideMaskVT = EVT::getVectorVT(*DAG.getContext(),
3595                                     MaskVT.getVectorElementType(),
3596                                     WideVT.getVectorNumElements());
3597   Mask = ModifyToType(Mask, WideMaskVT, true);
3598
3599   assert(Mask.getValueType().getVectorNumElements() ==
3600          WideVal.getValueType().getVectorNumElements() &&
3601          "Mask and data vectors should have the same number of elements");
3602   return DAG.getMaskedStore(MST->getChain(), dl, WideVal, MST->getBasePtr(),
3603                             Mask, MST->getMemoryVT(), MST->getMemOperand(),
3604                             false, MST->isCompressingStore());
3605 }
3606
3607 SDValue DAGTypeLegalizer::WidenVecOp_MSCATTER(SDNode *N, unsigned OpNo) {
3608   assert(OpNo == 1 && "Can widen only data operand of mscatter");
3609   MaskedScatterSDNode *MSC = cast<MaskedScatterSDNode>(N);
3610   SDValue DataOp = MSC->getValue();
3611   SDValue Mask = MSC->getMask();
3612   EVT MaskVT = Mask.getValueType();
3613   SDValue Scale = MSC->getScale();
3614
3615   // Widen the value.
3616   SDValue WideVal = GetWidenedVector(DataOp);
3617   EVT WideVT = WideVal.getValueType();
3618   unsigned NumElts = WideVT.getVectorNumElements();
3619   SDLoc dl(N);
3620
3621   // The mask should be widened as well.
3622   EVT WideMaskVT = EVT::getVectorVT(*DAG.getContext(),
3623                                     MaskVT.getVectorElementType(), NumElts);
3624   Mask = ModifyToType(Mask, WideMaskVT, true);
3625
3626   // Widen index.
3627   SDValue Index = MSC->getIndex();
3628   EVT WideIndexVT = EVT::getVectorVT(*DAG.getContext(),
3629                                      Index.getValueType().getScalarType(),
3630                                      NumElts);
3631   Index = ModifyToType(Index, WideIndexVT);
3632
3633   SDValue Ops[] = {MSC->getChain(), WideVal, Mask, MSC->getBasePtr(), Index,
3634                    Scale};
3635   return DAG.getMaskedScatter(DAG.getVTList(MVT::Other),
3636                               MSC->getMemoryVT(), dl, Ops,
3637                               MSC->getMemOperand());
3638 }
3639
3640 SDValue DAGTypeLegalizer::WidenVecOp_SETCC(SDNode *N) {
3641   SDValue InOp0 = GetWidenedVector(N->getOperand(0));
3642   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
3643   SDLoc dl(N);
3644   EVT VT = N->getValueType(0);
3645
3646   // WARNING: In this code we widen the compare instruction with garbage.
3647   // This garbage may contain denormal floats which may be slow. Is this a real
3648   // concern ? Should we zero the unused lanes if this is a float compare ?
3649
3650   // Get a new SETCC node to compare the newly widened operands.
3651   // Only some of the compared elements are legal.
3652   EVT SVT = TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(),
3653                                    InOp0.getValueType());
3654   // The result type is legal, if its vXi1, keep vXi1 for the new SETCC.
3655   if (VT.getScalarType() == MVT::i1)
3656     SVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1,
3657                            SVT.getVectorNumElements());
3658
3659   SDValue WideSETCC = DAG.getNode(ISD::SETCC, SDLoc(N),
3660                                   SVT, InOp0, InOp1, N->getOperand(2));
3661
3662   // Extract the needed results from the result vector.
3663   EVT ResVT = EVT::getVectorVT(*DAG.getContext(),
3664                                SVT.getVectorElementType(),
3665                                VT.getVectorNumElements());
3666   SDValue CC = DAG.getNode(
3667       ISD::EXTRACT_SUBVECTOR, dl, ResVT, WideSETCC,
3668       DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3669
3670   return PromoteTargetBoolean(CC, VT);
3671 }
3672
3673
3674 //===----------------------------------------------------------------------===//
3675 // Vector Widening Utilities
3676 //===----------------------------------------------------------------------===//
3677
3678 // Utility function to find the type to chop up a widen vector for load/store
3679 //  TLI:       Target lowering used to determine legal types.
3680 //  Width:     Width left need to load/store.
3681 //  WidenVT:   The widen vector type to load to/store from
3682 //  Align:     If 0, don't allow use of a wider type
3683 //  WidenEx:   If Align is not 0, the amount additional we can load/store from.
3684
3685 static EVT FindMemType(SelectionDAG& DAG, const TargetLowering &TLI,
3686                        unsigned Width, EVT WidenVT,
3687                        unsigned Align = 0, unsigned WidenEx = 0) {
3688   EVT WidenEltVT = WidenVT.getVectorElementType();
3689   unsigned WidenWidth = WidenVT.getSizeInBits();
3690   unsigned WidenEltWidth = WidenEltVT.getSizeInBits();
3691   unsigned AlignInBits = Align*8;
3692
3693   // If we have one element to load/store, return it.
3694   EVT RetVT = WidenEltVT;
3695   if (Width == WidenEltWidth)
3696     return RetVT;
3697
3698   // See if there is larger legal integer than the element type to load/store.
3699   unsigned VT;
3700   for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE;
3701        VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) {
3702     EVT MemVT((MVT::SimpleValueType) VT);
3703     unsigned MemVTWidth = MemVT.getSizeInBits();
3704     if (MemVT.getSizeInBits() <= WidenEltWidth)
3705       break;
3706     auto Action = TLI.getTypeAction(*DAG.getContext(), MemVT);
3707     if ((Action == TargetLowering::TypeLegal ||
3708          Action == TargetLowering::TypePromoteInteger) &&
3709         (WidenWidth % MemVTWidth) == 0 &&
3710         isPowerOf2_32(WidenWidth / MemVTWidth) &&
3711         (MemVTWidth <= Width ||
3712          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
3713       RetVT = MemVT;
3714       break;
3715     }
3716   }
3717
3718   // See if there is a larger vector type to load/store that has the same vector
3719   // element type and is evenly divisible with the WidenVT.
3720   for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE;
3721        VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) {
3722     EVT MemVT = (MVT::SimpleValueType) VT;
3723     unsigned MemVTWidth = MemVT.getSizeInBits();
3724     if (TLI.isTypeLegal(MemVT) && WidenEltVT == MemVT.getVectorElementType() &&
3725         (WidenWidth % MemVTWidth) == 0 &&
3726         isPowerOf2_32(WidenWidth / MemVTWidth) &&
3727         (MemVTWidth <= Width ||
3728          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
3729       if (RetVT.getSizeInBits() < MemVTWidth || MemVT == WidenVT)
3730         return MemVT;
3731     }
3732   }
3733
3734   return RetVT;
3735 }
3736
3737 // Builds a vector type from scalar loads
3738 //  VecTy: Resulting Vector type
3739 //  LDOps: Load operators to build a vector type
3740 //  [Start,End) the list of loads to use.
3741 static SDValue BuildVectorFromScalar(SelectionDAG& DAG, EVT VecTy,
3742                                      SmallVectorImpl<SDValue> &LdOps,
3743                                      unsigned Start, unsigned End) {
3744   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3745   SDLoc dl(LdOps[Start]);
3746   EVT LdTy = LdOps[Start].getValueType();
3747   unsigned Width = VecTy.getSizeInBits();
3748   unsigned NumElts = Width / LdTy.getSizeInBits();
3749   EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), LdTy, NumElts);
3750
3751   unsigned Idx = 1;
3752   SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT,LdOps[Start]);
3753
3754   for (unsigned i = Start + 1; i != End; ++i) {
3755     EVT NewLdTy = LdOps[i].getValueType();
3756     if (NewLdTy != LdTy) {
3757       NumElts = Width / NewLdTy.getSizeInBits();
3758       NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewLdTy, NumElts);
3759       VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, VecOp);
3760       // Readjust position and vector position based on new load type.
3761       Idx = Idx * LdTy.getSizeInBits() / NewLdTy.getSizeInBits();
3762       LdTy = NewLdTy;
3763     }
3764     VecOp = DAG.getNode(
3765         ISD::INSERT_VECTOR_ELT, dl, NewVecVT, VecOp, LdOps[i],
3766         DAG.getConstant(Idx++, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3767   }
3768   return DAG.getNode(ISD::BITCAST, dl, VecTy, VecOp);
3769 }
3770
3771 SDValue DAGTypeLegalizer::GenWidenVectorLoads(SmallVectorImpl<SDValue> &LdChain,
3772                                               LoadSDNode *LD) {
3773   // The strategy assumes that we can efficiently load power-of-two widths.
3774   // The routine chops the vector into the largest vector loads with the same
3775   // element type or scalar loads and then recombines it to the widen vector
3776   // type.
3777   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
3778   unsigned WidenWidth = WidenVT.getSizeInBits();
3779   EVT LdVT    = LD->getMemoryVT();
3780   SDLoc dl(LD);
3781   assert(LdVT.isVector() && WidenVT.isVector());
3782   assert(LdVT.getVectorElementType() == WidenVT.getVectorElementType());
3783
3784   // Load information
3785   SDValue Chain = LD->getChain();
3786   SDValue BasePtr = LD->getBasePtr();
3787   unsigned Align = LD->getAlignment();
3788   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
3789   AAMDNodes AAInfo = LD->getAAInfo();
3790
3791   int LdWidth = LdVT.getSizeInBits();
3792   int WidthDiff = WidenWidth - LdWidth;
3793   unsigned LdAlign = LD->isVolatile() ? 0 : Align; // Allow wider loads.
3794
3795   // Find the vector type that can load from.
3796   EVT NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
3797   int NewVTWidth = NewVT.getSizeInBits();
3798   SDValue LdOp = DAG.getLoad(NewVT, dl, Chain, BasePtr, LD->getPointerInfo(),
3799                              Align, MMOFlags, AAInfo);
3800   LdChain.push_back(LdOp.getValue(1));
3801
3802   // Check if we can load the element with one instruction.
3803   if (LdWidth <= NewVTWidth) {
3804     if (!NewVT.isVector()) {
3805       unsigned NumElts = WidenWidth / NewVTWidth;
3806       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
3807       SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT, LdOp);
3808       return DAG.getNode(ISD::BITCAST, dl, WidenVT, VecOp);
3809     }
3810     if (NewVT == WidenVT)
3811       return LdOp;
3812
3813     assert(WidenWidth % NewVTWidth == 0);
3814     unsigned NumConcat = WidenWidth / NewVTWidth;
3815     SmallVector<SDValue, 16> ConcatOps(NumConcat);
3816     SDValue UndefVal = DAG.getUNDEF(NewVT);
3817     ConcatOps[0] = LdOp;
3818     for (unsigned i = 1; i != NumConcat; ++i)
3819       ConcatOps[i] = UndefVal;
3820     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, ConcatOps);
3821   }
3822
3823   // Load vector by using multiple loads from largest vector to scalar.
3824   SmallVector<SDValue, 16> LdOps;
3825   LdOps.push_back(LdOp);
3826
3827   LdWidth -= NewVTWidth;
3828   unsigned Offset = 0;
3829
3830   while (LdWidth > 0) {
3831     unsigned Increment = NewVTWidth / 8;
3832     Offset += Increment;
3833     BasePtr = DAG.getObjectPtrOffset(dl, BasePtr, Increment);
3834
3835     SDValue L;
3836     if (LdWidth < NewVTWidth) {
3837       // The current type we are using is too large. Find a better size.
3838       NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
3839       NewVTWidth = NewVT.getSizeInBits();
3840       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
3841                       LD->getPointerInfo().getWithOffset(Offset),
3842                       MinAlign(Align, Increment), MMOFlags, AAInfo);
3843       LdChain.push_back(L.getValue(1));
3844       if (L->getValueType(0).isVector() && NewVTWidth >= LdWidth) {
3845         // Later code assumes the vector loads produced will be mergeable, so we
3846         // must pad the final entry up to the previous width. Scalars are
3847         // combined separately.
3848         SmallVector<SDValue, 16> Loads;
3849         Loads.push_back(L);
3850         unsigned size = L->getValueSizeInBits(0);
3851         while (size < LdOp->getValueSizeInBits(0)) {
3852           Loads.push_back(DAG.getUNDEF(L->getValueType(0)));
3853           size += L->getValueSizeInBits(0);
3854         }
3855         L = DAG.getNode(ISD::CONCAT_VECTORS, dl, LdOp->getValueType(0), Loads);
3856       }
3857     } else {
3858       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
3859                       LD->getPointerInfo().getWithOffset(Offset),
3860                       MinAlign(Align, Increment), MMOFlags, AAInfo);
3861       LdChain.push_back(L.getValue(1));
3862     }
3863
3864     LdOps.push_back(L);
3865     LdOp = L;
3866
3867     LdWidth -= NewVTWidth;
3868   }
3869
3870   // Build the vector from the load operations.
3871   unsigned End = LdOps.size();
3872   if (!LdOps[0].getValueType().isVector())
3873     // All the loads are scalar loads.
3874     return BuildVectorFromScalar(DAG, WidenVT, LdOps, 0, End);
3875
3876   // If the load contains vectors, build the vector using concat vector.
3877   // All of the vectors used to load are power-of-2, and the scalar loads can be
3878   // combined to make a power-of-2 vector.
3879   SmallVector<SDValue, 16> ConcatOps(End);
3880   int i = End - 1;
3881   int Idx = End;
3882   EVT LdTy = LdOps[i].getValueType();
3883   // First, combine the scalar loads to a vector.
3884   if (!LdTy.isVector())  {
3885     for (--i; i >= 0; --i) {
3886       LdTy = LdOps[i].getValueType();
3887       if (LdTy.isVector())
3888         break;
3889     }
3890     ConcatOps[--Idx] = BuildVectorFromScalar(DAG, LdTy, LdOps, i + 1, End);
3891   }
3892   ConcatOps[--Idx] = LdOps[i];
3893   for (--i; i >= 0; --i) {
3894     EVT NewLdTy = LdOps[i].getValueType();
3895     if (NewLdTy != LdTy) {
3896       // Create a larger vector.
3897       ConcatOps[End-1] = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewLdTy,
3898                                      makeArrayRef(&ConcatOps[Idx], End - Idx));
3899       Idx = End - 1;
3900       LdTy = NewLdTy;
3901     }
3902     ConcatOps[--Idx] = LdOps[i];
3903   }
3904
3905   if (WidenWidth == LdTy.getSizeInBits() * (End - Idx))
3906     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
3907                        makeArrayRef(&ConcatOps[Idx], End - Idx));
3908
3909   // We need to fill the rest with undefs to build the vector.
3910   unsigned NumOps = WidenWidth / LdTy.getSizeInBits();
3911   SmallVector<SDValue, 16> WidenOps(NumOps);
3912   SDValue UndefVal = DAG.getUNDEF(LdTy);
3913   {
3914     unsigned i = 0;
3915     for (; i != End-Idx; ++i)
3916       WidenOps[i] = ConcatOps[Idx+i];
3917     for (; i != NumOps; ++i)
3918       WidenOps[i] = UndefVal;
3919   }
3920   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, WidenOps);
3921 }
3922
3923 SDValue
3924 DAGTypeLegalizer::GenWidenVectorExtLoads(SmallVectorImpl<SDValue> &LdChain,
3925                                          LoadSDNode *LD,
3926                                          ISD::LoadExtType ExtType) {
3927   // For extension loads, it may not be more efficient to chop up the vector
3928   // and then extend it. Instead, we unroll the load and build a new vector.
3929   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
3930   EVT LdVT    = LD->getMemoryVT();
3931   SDLoc dl(LD);
3932   assert(LdVT.isVector() && WidenVT.isVector());
3933
3934   // Load information
3935   SDValue Chain = LD->getChain();
3936   SDValue BasePtr = LD->getBasePtr();
3937   unsigned Align = LD->getAlignment();
3938   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
3939   AAMDNodes AAInfo = LD->getAAInfo();
3940
3941   EVT EltVT = WidenVT.getVectorElementType();
3942   EVT LdEltVT = LdVT.getVectorElementType();
3943   unsigned NumElts = LdVT.getVectorNumElements();
3944
3945   // Load each element and widen.
3946   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3947   SmallVector<SDValue, 16> Ops(WidenNumElts);
3948   unsigned Increment = LdEltVT.getSizeInBits() / 8;
3949   Ops[0] =
3950       DAG.getExtLoad(ExtType, dl, EltVT, Chain, BasePtr, LD->getPointerInfo(),
3951                      LdEltVT, Align, MMOFlags, AAInfo);
3952   LdChain.push_back(Ops[0].getValue(1));
3953   unsigned i = 0, Offset = Increment;
3954   for (i=1; i < NumElts; ++i, Offset += Increment) {
3955     SDValue NewBasePtr = DAG.getObjectPtrOffset(dl, BasePtr, Offset);
3956     Ops[i] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, NewBasePtr,
3957                             LD->getPointerInfo().getWithOffset(Offset), LdEltVT,
3958                             Align, MMOFlags, AAInfo);
3959     LdChain.push_back(Ops[i].getValue(1));
3960   }
3961
3962   // Fill the rest with undefs.
3963   SDValue UndefVal = DAG.getUNDEF(EltVT);
3964   for (; i != WidenNumElts; ++i)
3965     Ops[i] = UndefVal;
3966
3967   return DAG.getBuildVector(WidenVT, dl, Ops);
3968 }
3969
3970 void DAGTypeLegalizer::GenWidenVectorStores(SmallVectorImpl<SDValue> &StChain,
3971                                             StoreSDNode *ST) {
3972   // The strategy assumes that we can efficiently store power-of-two widths.
3973   // The routine chops the vector into the largest vector stores with the same
3974   // element type or scalar stores.
3975   SDValue  Chain = ST->getChain();
3976   SDValue  BasePtr = ST->getBasePtr();
3977   unsigned Align = ST->getAlignment();
3978   MachineMemOperand::Flags MMOFlags = ST->getMemOperand()->getFlags();
3979   AAMDNodes AAInfo = ST->getAAInfo();
3980   SDValue  ValOp = GetWidenedVector(ST->getValue());
3981   SDLoc dl(ST);
3982
3983   EVT StVT = ST->getMemoryVT();
3984   unsigned StWidth = StVT.getSizeInBits();
3985   EVT ValVT = ValOp.getValueType();
3986   unsigned ValWidth = ValVT.getSizeInBits();
3987   EVT ValEltVT = ValVT.getVectorElementType();
3988   unsigned ValEltWidth = ValEltVT.getSizeInBits();
3989   assert(StVT.getVectorElementType() == ValEltVT);
3990
3991   int Idx = 0;          // current index to store
3992   unsigned Offset = 0;  // offset from base to store
3993   while (StWidth != 0) {
3994     // Find the largest vector type we can store with.
3995     EVT NewVT = FindMemType(DAG, TLI, StWidth, ValVT);
3996     unsigned NewVTWidth = NewVT.getSizeInBits();
3997     unsigned Increment = NewVTWidth / 8;
3998     if (NewVT.isVector()) {
3999       unsigned NumVTElts = NewVT.getVectorNumElements();
4000       do {
4001         SDValue EOp = DAG.getNode(
4002             ISD::EXTRACT_SUBVECTOR, dl, NewVT, ValOp,
4003             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4004         StChain.push_back(DAG.getStore(
4005             Chain, dl, EOp, BasePtr, ST->getPointerInfo().getWithOffset(Offset),
4006             MinAlign(Align, Offset), MMOFlags, AAInfo));
4007         StWidth -= NewVTWidth;
4008         Offset += Increment;
4009         Idx += NumVTElts;
4010
4011         BasePtr = DAG.getObjectPtrOffset(dl, BasePtr, Increment);
4012       } while (StWidth != 0 && StWidth >= NewVTWidth);
4013     } else {
4014       // Cast the vector to the scalar type we can store.
4015       unsigned NumElts = ValWidth / NewVTWidth;
4016       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
4017       SDValue VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, ValOp);
4018       // Readjust index position based on new vector type.
4019       Idx = Idx * ValEltWidth / NewVTWidth;
4020       do {
4021         SDValue EOp = DAG.getNode(
4022             ISD::EXTRACT_VECTOR_ELT, dl, NewVT, VecOp,
4023             DAG.getConstant(Idx++, dl,
4024                             TLI.getVectorIdxTy(DAG.getDataLayout())));
4025         StChain.push_back(DAG.getStore(
4026             Chain, dl, EOp, BasePtr, ST->getPointerInfo().getWithOffset(Offset),
4027             MinAlign(Align, Offset), MMOFlags, AAInfo));
4028         StWidth -= NewVTWidth;
4029         Offset += Increment;
4030         BasePtr = DAG.getObjectPtrOffset(dl, BasePtr, Increment);
4031       } while (StWidth != 0 && StWidth >= NewVTWidth);
4032       // Restore index back to be relative to the original widen element type.
4033       Idx = Idx * NewVTWidth / ValEltWidth;
4034     }
4035   }
4036 }
4037
4038 void
4039 DAGTypeLegalizer::GenWidenVectorTruncStores(SmallVectorImpl<SDValue> &StChain,
4040                                             StoreSDNode *ST) {
4041   // For extension loads, it may not be more efficient to truncate the vector
4042   // and then store it. Instead, we extract each element and then store it.
4043   SDValue Chain = ST->getChain();
4044   SDValue BasePtr = ST->getBasePtr();
4045   unsigned Align = ST->getAlignment();
4046   MachineMemOperand::Flags MMOFlags = ST->getMemOperand()->getFlags();
4047   AAMDNodes AAInfo = ST->getAAInfo();
4048   SDValue ValOp = GetWidenedVector(ST->getValue());
4049   SDLoc dl(ST);
4050
4051   EVT StVT = ST->getMemoryVT();
4052   EVT ValVT = ValOp.getValueType();
4053
4054   // It must be true that the wide vector type is bigger than where we need to
4055   // store.
4056   assert(StVT.isVector() && ValOp.getValueType().isVector());
4057   assert(StVT.bitsLT(ValOp.getValueType()));
4058
4059   // For truncating stores, we can not play the tricks of chopping legal vector
4060   // types and bitcast it to the right type. Instead, we unroll the store.
4061   EVT StEltVT  = StVT.getVectorElementType();
4062   EVT ValEltVT = ValVT.getVectorElementType();
4063   unsigned Increment = ValEltVT.getSizeInBits() / 8;
4064   unsigned NumElts = StVT.getVectorNumElements();
4065   SDValue EOp = DAG.getNode(
4066       ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
4067       DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4068   StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, BasePtr,
4069                                       ST->getPointerInfo(), StEltVT, Align,
4070                                       MMOFlags, AAInfo));
4071   unsigned Offset = Increment;
4072   for (unsigned i=1; i < NumElts; ++i, Offset += Increment) {
4073     SDValue NewBasePtr = DAG.getObjectPtrOffset(dl, BasePtr, Offset);
4074     SDValue EOp = DAG.getNode(
4075         ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
4076         DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4077     StChain.push_back(DAG.getTruncStore(
4078         Chain, dl, EOp, NewBasePtr, ST->getPointerInfo().getWithOffset(Offset),
4079         StEltVT, MinAlign(Align, Offset), MMOFlags, AAInfo));
4080   }
4081 }
4082
4083 /// Modifies a vector input (widen or narrows) to a vector of NVT.  The
4084 /// input vector must have the same element type as NVT.
4085 /// FillWithZeroes specifies that the vector should be widened with zeroes.
4086 SDValue DAGTypeLegalizer::ModifyToType(SDValue InOp, EVT NVT,
4087                                        bool FillWithZeroes) {
4088   // Note that InOp might have been widened so it might already have
4089   // the right width or it might need be narrowed.
4090   EVT InVT = InOp.getValueType();
4091   assert(InVT.getVectorElementType() == NVT.getVectorElementType() &&
4092          "input and widen element type must match");
4093   SDLoc dl(InOp);
4094
4095   // Check if InOp already has the right width.
4096   if (InVT == NVT)
4097     return InOp;
4098
4099   unsigned InNumElts = InVT.getVectorNumElements();
4100   unsigned WidenNumElts = NVT.getVectorNumElements();
4101   if (WidenNumElts > InNumElts && WidenNumElts % InNumElts == 0) {
4102     unsigned NumConcat = WidenNumElts / InNumElts;
4103     SmallVector<SDValue, 16> Ops(NumConcat);
4104     SDValue FillVal = FillWithZeroes ? DAG.getConstant(0, dl, InVT) :
4105       DAG.getUNDEF(InVT);
4106     Ops[0] = InOp;
4107     for (unsigned i = 1; i != NumConcat; ++i)
4108       Ops[i] = FillVal;
4109
4110     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, Ops);
4111   }
4112
4113   if (WidenNumElts < InNumElts && InNumElts % WidenNumElts)
4114     return DAG.getNode(
4115         ISD::EXTRACT_SUBVECTOR, dl, NVT, InOp,
4116         DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4117
4118   // Fall back to extract and build.
4119   SmallVector<SDValue, 16> Ops(WidenNumElts);
4120   EVT EltVT = NVT.getVectorElementType();
4121   unsigned MinNumElts = std::min(WidenNumElts, InNumElts);
4122   unsigned Idx;
4123   for (Idx = 0; Idx < MinNumElts; ++Idx)
4124     Ops[Idx] = DAG.getNode(
4125         ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
4126         DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4127
4128   SDValue FillVal = FillWithZeroes ? DAG.getConstant(0, dl, EltVT) :
4129     DAG.getUNDEF(EltVT);
4130   for ( ; Idx < WidenNumElts; ++Idx)
4131     Ops[Idx] = FillVal;
4132   return DAG.getBuildVector(NVT, dl, Ops);
4133 }