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