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   if (isLogicalMaskOp(N.getOpcode()))
2969     return isSETCCorConvertedSETCC(N.getOperand(0)) &&
2970            isSETCCorConvertedSETCC(N.getOperand(1));
2971
2972   return (N.getOpcode() == ISD::SETCC ||
2973           ISD::isBuildVectorOfConstantSDNodes(N.getNode()));
2974 }
2975 #endif
2976
2977 // Return a mask of vector type MaskVT to replace InMask. Also adjust MaskVT
2978 // to ToMaskVT if needed with vector extension or truncation.
2979 SDValue DAGTypeLegalizer::convertMask(SDValue InMask, EVT MaskVT,
2980                                       EVT ToMaskVT) {
2981   // Currently a SETCC or a AND/OR/XOR with two SETCCs are handled.
2982   // FIXME: This code seems to be too restrictive, we might consider
2983   // generalizing it or dropping it.
2984   assert(isSETCCorConvertedSETCC(InMask) && "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(InMask->getOpcode(), 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   LLVMContext &Ctx = *DAG.getContext();
2995   unsigned MaskScalarBits = MaskVT.getScalarSizeInBits();
2996   unsigned ToMaskScalBits = ToMaskVT.getScalarSizeInBits();
2997   if (MaskScalarBits < ToMaskScalBits) {
2998     EVT ExtVT = EVT::getVectorVT(Ctx, ToMaskVT.getVectorElementType(),
2999                                  MaskVT.getVectorNumElements());
3000     Mask = DAG.getNode(ISD::SIGN_EXTEND, SDLoc(Mask), ExtVT, Mask);
3001   } else if (MaskScalarBits > ToMaskScalBits) {
3002     EVT TruncVT = EVT::getVectorVT(Ctx, ToMaskVT.getVectorElementType(),
3003                                    MaskVT.getVectorNumElements());
3004     Mask = DAG.getNode(ISD::TRUNCATE, SDLoc(Mask), TruncVT, Mask);
3005   }
3006
3007   assert(Mask->getValueType(0).getScalarSizeInBits() ==
3008              ToMaskVT.getScalarSizeInBits() &&
3009          "Mask should have the right element size by now.");
3010
3011   // Adjust Mask to the right number of elements.
3012   unsigned CurrMaskNumEls = Mask->getValueType(0).getVectorNumElements();
3013   if (CurrMaskNumEls > ToMaskVT.getVectorNumElements()) {
3014     MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
3015     SDValue ZeroIdx = DAG.getConstant(0, SDLoc(Mask), IdxTy);
3016     Mask = DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(Mask), ToMaskVT, Mask,
3017                        ZeroIdx);
3018   } else if (CurrMaskNumEls < ToMaskVT.getVectorNumElements()) {
3019     unsigned NumSubVecs = (ToMaskVT.getVectorNumElements() / CurrMaskNumEls);
3020     EVT SubVT = Mask->getValueType(0);
3021     SmallVector<SDValue, 16> SubConcatOps(NumSubVecs);
3022     SubConcatOps[0] = Mask;
3023     for (unsigned i = 1; i < NumSubVecs; ++i)
3024       SubConcatOps[i] = DAG.getUNDEF(SubVT);
3025     Mask =
3026         DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(Mask), ToMaskVT, SubConcatOps);
3027   }
3028
3029   assert((Mask->getValueType(0) == ToMaskVT) &&
3030          "A mask of ToMaskVT should have been produced by now.");
3031
3032   return Mask;
3033 }
3034
3035 // Get the target mask VT, and widen if needed.
3036 EVT DAGTypeLegalizer::getSETCCWidenedResultTy(SDValue SetCC) {
3037   assert(SetCC->getOpcode() == ISD::SETCC);
3038   LLVMContext &Ctx = *DAG.getContext();
3039   EVT MaskVT = getSetCCResultType(SetCC->getOperand(0).getValueType());
3040   if (getTypeAction(MaskVT) == TargetLowering::TypeWidenVector)
3041     MaskVT = TLI.getTypeToTransformTo(Ctx, MaskVT);
3042   return MaskVT;
3043 }
3044
3045 // This method tries to handle VSELECT and its mask by legalizing operands
3046 // (which may require widening) and if needed adjusting the mask vector type
3047 // to match that of the VSELECT. Without it, many cases end up with
3048 // scalarization of the SETCC, with many unnecessary instructions.
3049 SDValue DAGTypeLegalizer::WidenVSELECTAndMask(SDNode *N) {
3050   LLVMContext &Ctx = *DAG.getContext();
3051   SDValue Cond = N->getOperand(0);
3052
3053   if (N->getOpcode() != ISD::VSELECT)
3054     return SDValue();
3055
3056   if (Cond->getOpcode() != ISD::SETCC && !isLogicalMaskOp(Cond->getOpcode()))
3057     return SDValue();
3058
3059   // If this is a splitted VSELECT that was previously already handled, do
3060   // nothing.
3061   if (Cond->getValueType(0).getScalarSizeInBits() != 1)
3062     return SDValue();
3063
3064   EVT VSelVT = N->getValueType(0);
3065   // Only handle vector types which are a power of 2.
3066   if (!isPowerOf2_64(VSelVT.getSizeInBits()))
3067     return SDValue();
3068
3069   // Don't touch if this will be scalarized.
3070   EVT FinalVT = VSelVT;
3071   while (getTypeAction(FinalVT) == TargetLowering::TypeSplitVector)
3072     FinalVT = FinalVT.getHalfNumVectorElementsVT(Ctx);
3073
3074   if (FinalVT.getVectorNumElements() == 1)
3075     return SDValue();
3076
3077   // If there is support for an i1 vector mask, don't touch.
3078   if (Cond.getOpcode() == ISD::SETCC) {
3079     EVT SetCCOpVT = Cond->getOperand(0).getValueType();
3080     while (TLI.getTypeAction(Ctx, SetCCOpVT) != TargetLowering::TypeLegal)
3081       SetCCOpVT = TLI.getTypeToTransformTo(Ctx, SetCCOpVT);
3082     EVT SetCCResVT = getSetCCResultType(SetCCOpVT);
3083     if (SetCCResVT.getScalarSizeInBits() == 1)
3084       return SDValue();
3085   }
3086
3087   // Get the VT and operands for VSELECT, and widen if needed.
3088   SDValue VSelOp1 = N->getOperand(1);
3089   SDValue VSelOp2 = N->getOperand(2);
3090   if (getTypeAction(VSelVT) == TargetLowering::TypeWidenVector) {
3091     VSelVT = TLI.getTypeToTransformTo(Ctx, VSelVT);
3092     VSelOp1 = GetWidenedVector(VSelOp1);
3093     VSelOp2 = GetWidenedVector(VSelOp2);
3094   }
3095
3096   // The mask of the VSELECT should have integer elements.
3097   EVT ToMaskVT = VSelVT;
3098   if (!ToMaskVT.getScalarType().isInteger())
3099     ToMaskVT = ToMaskVT.changeVectorElementTypeToInteger();
3100
3101   SDValue Mask;
3102   if (Cond->getOpcode() == ISD::SETCC) {
3103     EVT MaskVT = getSETCCWidenedResultTy(Cond);
3104     Mask = convertMask(Cond, MaskVT, ToMaskVT);
3105   } else if (isLogicalMaskOp(Cond->getOpcode()) &&
3106              Cond->getOperand(0).getOpcode() == ISD::SETCC &&
3107              Cond->getOperand(1).getOpcode() == ISD::SETCC) {
3108     // Cond is (AND/OR/XOR (SETCC, SETCC))
3109     SDValue SETCC0 = Cond->getOperand(0);
3110     SDValue SETCC1 = Cond->getOperand(1);
3111     EVT VT0 = getSETCCWidenedResultTy(SETCC0);
3112     EVT VT1 = getSETCCWidenedResultTy(SETCC1);
3113     unsigned ScalarBits0 = VT0.getScalarSizeInBits();
3114     unsigned ScalarBits1 = VT1.getScalarSizeInBits();
3115     unsigned ScalarBits_ToMask = ToMaskVT.getScalarSizeInBits();
3116     EVT MaskVT;
3117     // If the two SETCCs have different VTs, either extend/truncate one of
3118     // them to the other "towards" ToMaskVT, or truncate one and extend the
3119     // other to ToMaskVT.
3120     if (ScalarBits0 != ScalarBits1) {
3121       EVT NarrowVT = ((ScalarBits0 < ScalarBits1) ? VT0 : VT1);
3122       EVT WideVT = ((NarrowVT == VT0) ? VT1 : VT0);
3123       if (ScalarBits_ToMask >= WideVT.getScalarSizeInBits())
3124         MaskVT = WideVT;
3125       else if (ScalarBits_ToMask <= NarrowVT.getScalarSizeInBits())
3126         MaskVT = NarrowVT;
3127       else
3128         MaskVT = ToMaskVT;
3129     } else
3130       // If the two SETCCs have the same VT, don't change it.
3131       MaskVT = VT0;
3132
3133     // Make new SETCCs and logical nodes.
3134     SETCC0 = convertMask(SETCC0, VT0, MaskVT);
3135     SETCC1 = convertMask(SETCC1, VT1, MaskVT);
3136     Cond = DAG.getNode(Cond->getOpcode(), SDLoc(Cond), MaskVT, SETCC0, SETCC1);
3137
3138     // Convert the logical op for VSELECT if needed.
3139     Mask = convertMask(Cond, MaskVT, ToMaskVT);
3140   } else
3141     return SDValue();
3142
3143   return DAG.getNode(ISD::VSELECT, SDLoc(N), VSelVT, Mask, VSelOp1, VSelOp2);
3144 }
3145
3146 SDValue DAGTypeLegalizer::WidenVecRes_SELECT(SDNode *N) {
3147   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3148   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3149
3150   SDValue Cond1 = N->getOperand(0);
3151   EVT CondVT = Cond1.getValueType();
3152   if (CondVT.isVector()) {
3153     if (SDValue Res = WidenVSELECTAndMask(N))
3154       return Res;
3155
3156     EVT CondEltVT = CondVT.getVectorElementType();
3157     EVT CondWidenVT =  EVT::getVectorVT(*DAG.getContext(),
3158                                         CondEltVT, WidenNumElts);
3159     if (getTypeAction(CondVT) == TargetLowering::TypeWidenVector)
3160       Cond1 = GetWidenedVector(Cond1);
3161
3162     // If we have to split the condition there is no point in widening the
3163     // select. This would result in an cycle of widening the select ->
3164     // widening the condition operand -> splitting the condition operand ->
3165     // splitting the select -> widening the select. Instead split this select
3166     // further and widen the resulting type.
3167     if (getTypeAction(CondVT) == TargetLowering::TypeSplitVector) {
3168       SDValue SplitSelect = SplitVecOp_VSELECT(N, 0);
3169       SDValue Res = ModifyToType(SplitSelect, WidenVT);
3170       return Res;
3171     }
3172
3173     if (Cond1.getValueType() != CondWidenVT)
3174       Cond1 = ModifyToType(Cond1, CondWidenVT);
3175   }
3176
3177   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
3178   SDValue InOp2 = GetWidenedVector(N->getOperand(2));
3179   assert(InOp1.getValueType() == WidenVT && InOp2.getValueType() == WidenVT);
3180   return DAG.getNode(N->getOpcode(), SDLoc(N),
3181                      WidenVT, Cond1, InOp1, InOp2);
3182 }
3183
3184 SDValue DAGTypeLegalizer::WidenVecRes_SELECT_CC(SDNode *N) {
3185   SDValue InOp1 = GetWidenedVector(N->getOperand(2));
3186   SDValue InOp2 = GetWidenedVector(N->getOperand(3));
3187   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
3188                      InOp1.getValueType(), N->getOperand(0),
3189                      N->getOperand(1), InOp1, InOp2, N->getOperand(4));
3190 }
3191
3192 SDValue DAGTypeLegalizer::WidenVecRes_SETCC(SDNode *N) {
3193   assert(N->getValueType(0).isVector() ==
3194          N->getOperand(0).getValueType().isVector() &&
3195          "Scalar/Vector type mismatch");
3196   if (N->getValueType(0).isVector()) return WidenVecRes_VSETCC(N);
3197
3198   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3199   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
3200   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3201   return DAG.getNode(ISD::SETCC, SDLoc(N), WidenVT,
3202                      InOp1, InOp2, N->getOperand(2));
3203 }
3204
3205 SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) {
3206  EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3207  return DAG.getUNDEF(WidenVT);
3208 }
3209
3210 SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N) {
3211   EVT VT = N->getValueType(0);
3212   SDLoc dl(N);
3213
3214   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3215   unsigned NumElts = VT.getVectorNumElements();
3216   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3217
3218   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
3219   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3220
3221   // Adjust mask based on new input vector length.
3222   SmallVector<int, 16> NewMask;
3223   for (unsigned i = 0; i != NumElts; ++i) {
3224     int Idx = N->getMaskElt(i);
3225     if (Idx < (int)NumElts)
3226       NewMask.push_back(Idx);
3227     else
3228       NewMask.push_back(Idx - NumElts + WidenNumElts);
3229   }
3230   for (unsigned i = NumElts; i != WidenNumElts; ++i)
3231     NewMask.push_back(-1);
3232   return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, NewMask);
3233 }
3234
3235 SDValue DAGTypeLegalizer::WidenVecRes_VSETCC(SDNode *N) {
3236   assert(N->getValueType(0).isVector() &&
3237          N->getOperand(0).getValueType().isVector() &&
3238          "Operands must be vectors");
3239   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3240   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3241
3242   SDValue InOp1 = N->getOperand(0);
3243   EVT InVT = InOp1.getValueType();
3244   assert(InVT.isVector() && "can not widen non-vector type");
3245   EVT WidenInVT = EVT::getVectorVT(*DAG.getContext(),
3246                                    InVT.getVectorElementType(), WidenNumElts);
3247
3248   // The input and output types often differ here, and it could be that while
3249   // we'd prefer to widen the result type, the input operands have been split.
3250   // In this case, we also need to split the result of this node as well.
3251   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector) {
3252     SDValue SplitVSetCC = SplitVecOp_VSETCC(N);
3253     SDValue Res = ModifyToType(SplitVSetCC, WidenVT);
3254     return Res;
3255   }
3256
3257   InOp1 = GetWidenedVector(InOp1);
3258   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3259
3260   // Assume that the input and output will be widen appropriately.  If not,
3261   // we will have to unroll it at some point.
3262   assert(InOp1.getValueType() == WidenInVT &&
3263          InOp2.getValueType() == WidenInVT &&
3264          "Input not widened to expected type!");
3265   (void)WidenInVT;
3266   return DAG.getNode(ISD::SETCC, SDLoc(N),
3267                      WidenVT, InOp1, InOp2, N->getOperand(2));
3268 }
3269
3270
3271 //===----------------------------------------------------------------------===//
3272 // Widen Vector Operand
3273 //===----------------------------------------------------------------------===//
3274 bool DAGTypeLegalizer::WidenVectorOperand(SDNode *N, unsigned OpNo) {
3275   DEBUG(dbgs() << "Widen node operand " << OpNo << ": ";
3276         N->dump(&DAG);
3277         dbgs() << "\n");
3278   SDValue Res = SDValue();
3279
3280   // See if the target wants to custom widen this node.
3281   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
3282     return false;
3283
3284   switch (N->getOpcode()) {
3285   default:
3286 #ifndef NDEBUG
3287     dbgs() << "WidenVectorOperand op #" << OpNo << ": ";
3288     N->dump(&DAG);
3289     dbgs() << "\n";
3290 #endif
3291     llvm_unreachable("Do not know how to widen this operator's operand!");
3292
3293   case ISD::BITCAST:            Res = WidenVecOp_BITCAST(N); break;
3294   case ISD::CONCAT_VECTORS:     Res = WidenVecOp_CONCAT_VECTORS(N); break;
3295   case ISD::EXTRACT_SUBVECTOR:  Res = WidenVecOp_EXTRACT_SUBVECTOR(N); break;
3296   case ISD::EXTRACT_VECTOR_ELT: Res = WidenVecOp_EXTRACT_VECTOR_ELT(N); break;
3297   case ISD::STORE:              Res = WidenVecOp_STORE(N); break;
3298   case ISD::MSTORE:             Res = WidenVecOp_MSTORE(N, OpNo); break;
3299   case ISD::MSCATTER:           Res = WidenVecOp_MSCATTER(N, OpNo); break;
3300   case ISD::SETCC:              Res = WidenVecOp_SETCC(N); break;
3301   case ISD::FCOPYSIGN:          Res = WidenVecOp_FCOPYSIGN(N); break;
3302
3303   case ISD::ANY_EXTEND:
3304   case ISD::SIGN_EXTEND:
3305   case ISD::ZERO_EXTEND:
3306     Res = WidenVecOp_EXTEND(N);
3307     break;
3308
3309   case ISD::FP_EXTEND:
3310   case ISD::FP_TO_SINT:
3311   case ISD::FP_TO_UINT:
3312   case ISD::SINT_TO_FP:
3313   case ISD::UINT_TO_FP:
3314   case ISD::TRUNCATE:
3315     Res = WidenVecOp_Convert(N);
3316     break;
3317   }
3318
3319   // If Res is null, the sub-method took care of registering the result.
3320   if (!Res.getNode()) return false;
3321
3322   // If the result is N, the sub-method updated N in place.  Tell the legalizer
3323   // core about this.
3324   if (Res.getNode() == N)
3325     return true;
3326
3327
3328   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
3329          "Invalid operand expansion");
3330
3331   ReplaceValueWith(SDValue(N, 0), Res);
3332   return false;
3333 }
3334
3335 SDValue DAGTypeLegalizer::WidenVecOp_EXTEND(SDNode *N) {
3336   SDLoc DL(N);
3337   EVT VT = N->getValueType(0);
3338
3339   SDValue InOp = N->getOperand(0);
3340   // If some legalization strategy other than widening is used on the operand,
3341   // we can't safely assume that just extending the low lanes is the correct
3342   // transformation.
3343   if (getTypeAction(InOp.getValueType()) != TargetLowering::TypeWidenVector)
3344     return WidenVecOp_Convert(N);
3345   InOp = GetWidenedVector(InOp);
3346   assert(VT.getVectorNumElements() <
3347              InOp.getValueType().getVectorNumElements() &&
3348          "Input wasn't widened!");
3349
3350   // We may need to further widen the operand until it has the same total
3351   // vector size as the result.
3352   EVT InVT = InOp.getValueType();
3353   if (InVT.getSizeInBits() != VT.getSizeInBits()) {
3354     EVT InEltVT = InVT.getVectorElementType();
3355     for (int i = MVT::FIRST_VECTOR_VALUETYPE, e = MVT::LAST_VECTOR_VALUETYPE; i < e; ++i) {
3356       EVT FixedVT = (MVT::SimpleValueType)i;
3357       EVT FixedEltVT = FixedVT.getVectorElementType();
3358       if (TLI.isTypeLegal(FixedVT) &&
3359           FixedVT.getSizeInBits() == VT.getSizeInBits() &&
3360           FixedEltVT == InEltVT) {
3361         assert(FixedVT.getVectorNumElements() >= VT.getVectorNumElements() &&
3362                "Not enough elements in the fixed type for the operand!");
3363         assert(FixedVT.getVectorNumElements() != InVT.getVectorNumElements() &&
3364                "We can't have the same type as we started with!");
3365         if (FixedVT.getVectorNumElements() > InVT.getVectorNumElements())
3366           InOp = DAG.getNode(
3367               ISD::INSERT_SUBVECTOR, DL, FixedVT, DAG.getUNDEF(FixedVT), InOp,
3368               DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
3369         else
3370           InOp = DAG.getNode(
3371               ISD::EXTRACT_SUBVECTOR, DL, FixedVT, InOp,
3372               DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
3373         break;
3374       }
3375     }
3376     InVT = InOp.getValueType();
3377     if (InVT.getSizeInBits() != VT.getSizeInBits())
3378       // We couldn't find a legal vector type that was a widening of the input
3379       // and could be extended in-register to the result type, so we have to
3380       // scalarize.
3381       return WidenVecOp_Convert(N);
3382   }
3383
3384   // Use special DAG nodes to represent the operation of extending the
3385   // low lanes.
3386   switch (N->getOpcode()) {
3387   default:
3388     llvm_unreachable("Extend legalization on on extend operation!");
3389   case ISD::ANY_EXTEND:
3390     return DAG.getAnyExtendVectorInReg(InOp, DL, VT);
3391   case ISD::SIGN_EXTEND:
3392     return DAG.getSignExtendVectorInReg(InOp, DL, VT);
3393   case ISD::ZERO_EXTEND:
3394     return DAG.getZeroExtendVectorInReg(InOp, DL, VT);
3395   }
3396 }
3397
3398 SDValue DAGTypeLegalizer::WidenVecOp_FCOPYSIGN(SDNode *N) {
3399   // The result (and first input) is legal, but the second input is illegal.
3400   // We can't do much to fix that, so just unroll and let the extracts off of
3401   // the second input be widened as needed later.
3402   return DAG.UnrollVectorOp(N);
3403 }
3404
3405 SDValue DAGTypeLegalizer::WidenVecOp_Convert(SDNode *N) {
3406   // Since the result is legal and the input is illegal, it is unlikely that we
3407   // can fix the input to a legal type so unroll the convert into some scalar
3408   // code and create a nasty build vector.
3409   EVT VT = N->getValueType(0);
3410   EVT EltVT = VT.getVectorElementType();
3411   SDLoc dl(N);
3412   unsigned NumElts = VT.getVectorNumElements();
3413   SDValue InOp = N->getOperand(0);
3414   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
3415     InOp = GetWidenedVector(InOp);
3416   EVT InVT = InOp.getValueType();
3417   EVT InEltVT = InVT.getVectorElementType();
3418
3419   unsigned Opcode = N->getOpcode();
3420   SmallVector<SDValue, 16> Ops(NumElts);
3421   for (unsigned i=0; i < NumElts; ++i)
3422     Ops[i] = DAG.getNode(
3423         Opcode, dl, EltVT,
3424         DAG.getNode(
3425             ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
3426             DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout()))));
3427
3428   return DAG.getBuildVector(VT, dl, Ops);
3429 }
3430
3431 SDValue DAGTypeLegalizer::WidenVecOp_BITCAST(SDNode *N) {
3432   EVT VT = N->getValueType(0);
3433   SDValue InOp = GetWidenedVector(N->getOperand(0));
3434   EVT InWidenVT = InOp.getValueType();
3435   SDLoc dl(N);
3436
3437   // Check if we can convert between two legal vector types and extract.
3438   unsigned InWidenSize = InWidenVT.getSizeInBits();
3439   unsigned Size = VT.getSizeInBits();
3440   // x86mmx is not an acceptable vector element type, so don't try.
3441   if (InWidenSize % Size == 0 && !VT.isVector() && VT != MVT::x86mmx) {
3442     unsigned NewNumElts = InWidenSize / Size;
3443     EVT NewVT = EVT::getVectorVT(*DAG.getContext(), VT, NewNumElts);
3444     if (TLI.isTypeLegal(NewVT)) {
3445       SDValue BitOp = DAG.getNode(ISD::BITCAST, dl, NewVT, InOp);
3446       return DAG.getNode(
3447           ISD::EXTRACT_VECTOR_ELT, dl, VT, BitOp,
3448           DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3449     }
3450   }
3451
3452   return CreateStackStoreLoad(InOp, VT);
3453 }
3454
3455 SDValue DAGTypeLegalizer::WidenVecOp_CONCAT_VECTORS(SDNode *N) {
3456   // If the input vector is not legal, it is likely that we will not find a
3457   // legal vector of the same size. Replace the concatenate vector with a
3458   // nasty build vector.
3459   EVT VT = N->getValueType(0);
3460   EVT EltVT = VT.getVectorElementType();
3461   SDLoc dl(N);
3462   unsigned NumElts = VT.getVectorNumElements();
3463   SmallVector<SDValue, 16> Ops(NumElts);
3464
3465   EVT InVT = N->getOperand(0).getValueType();
3466   unsigned NumInElts = InVT.getVectorNumElements();
3467
3468   unsigned Idx = 0;
3469   unsigned NumOperands = N->getNumOperands();
3470   for (unsigned i=0; i < NumOperands; ++i) {
3471     SDValue InOp = N->getOperand(i);
3472     if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
3473       InOp = GetWidenedVector(InOp);
3474     for (unsigned j=0; j < NumInElts; ++j)
3475       Ops[Idx++] = DAG.getNode(
3476           ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
3477           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3478   }
3479   return DAG.getBuildVector(VT, dl, Ops);
3480 }
3481
3482 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
3483   SDValue InOp = GetWidenedVector(N->getOperand(0));
3484   return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(N),
3485                      N->getValueType(0), InOp, N->getOperand(1));
3486 }
3487
3488 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
3489   SDValue InOp = GetWidenedVector(N->getOperand(0));
3490   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
3491                      N->getValueType(0), InOp, N->getOperand(1));
3492 }
3493
3494 SDValue DAGTypeLegalizer::WidenVecOp_STORE(SDNode *N) {
3495   // We have to widen the value, but we want only to store the original
3496   // vector type.
3497   StoreSDNode *ST = cast<StoreSDNode>(N);
3498
3499   SmallVector<SDValue, 16> StChain;
3500   if (ST->isTruncatingStore())
3501     GenWidenVectorTruncStores(StChain, ST);
3502   else
3503     GenWidenVectorStores(StChain, ST);
3504
3505   if (StChain.size() == 1)
3506     return StChain[0];
3507   else
3508     return DAG.getNode(ISD::TokenFactor, SDLoc(ST), MVT::Other, StChain);
3509 }
3510
3511 SDValue DAGTypeLegalizer::WidenVecOp_MSTORE(SDNode *N, unsigned OpNo) {
3512   MaskedStoreSDNode *MST = cast<MaskedStoreSDNode>(N);
3513   SDValue Mask = MST->getMask();
3514   EVT MaskVT = Mask.getValueType();
3515   SDValue StVal = MST->getValue();
3516   // Widen the value
3517   SDValue WideVal = GetWidenedVector(StVal);
3518   SDLoc dl(N);
3519
3520   if (OpNo == 2 || getTypeAction(MaskVT) == TargetLowering::TypeWidenVector)
3521     Mask = GetWidenedVector(Mask);
3522   else {
3523     // The mask should be widened as well.
3524     EVT BoolVT = getSetCCResultType(WideVal.getValueType());
3525     // We can't use ModifyToType() because we should fill the mask with
3526     // zeroes.
3527     unsigned WidenNumElts = BoolVT.getVectorNumElements();
3528     unsigned MaskNumElts = MaskVT.getVectorNumElements();
3529
3530     unsigned NumConcat = WidenNumElts / MaskNumElts;
3531     SmallVector<SDValue, 16> Ops(NumConcat);
3532     SDValue ZeroVal = DAG.getConstant(0, dl, MaskVT);
3533     Ops[0] = Mask;
3534     for (unsigned i = 1; i != NumConcat; ++i)
3535       Ops[i] = ZeroVal;
3536
3537     Mask = DAG.getNode(ISD::CONCAT_VECTORS, dl, BoolVT, Ops);
3538   }
3539   assert(Mask.getValueType().getVectorNumElements() ==
3540          WideVal.getValueType().getVectorNumElements() &&
3541          "Mask and data vectors should have the same number of elements");
3542   return DAG.getMaskedStore(MST->getChain(), dl, WideVal, MST->getBasePtr(),
3543                             Mask, MST->getMemoryVT(), MST->getMemOperand(),
3544                             false, MST->isCompressingStore());
3545 }
3546
3547 SDValue DAGTypeLegalizer::WidenVecOp_MSCATTER(SDNode *N, unsigned OpNo) {
3548   assert(OpNo == 1 && "Can widen only data operand of mscatter");
3549   MaskedScatterSDNode *MSC = cast<MaskedScatterSDNode>(N);
3550   SDValue DataOp = MSC->getValue();
3551   SDValue Mask = MSC->getMask();
3552
3553   // Widen the value.
3554   SDValue WideVal = GetWidenedVector(DataOp);
3555   EVT WideVT = WideVal.getValueType();
3556   unsigned NumElts = WideVal.getValueType().getVectorNumElements();
3557   SDLoc dl(N);
3558
3559   // The mask should be widened as well.
3560   Mask = WidenTargetBoolean(Mask, WideVT, true);
3561
3562   // Widen index.
3563   SDValue Index = MSC->getIndex();
3564   EVT WideIndexVT = EVT::getVectorVT(*DAG.getContext(),
3565                                      Index.getValueType().getScalarType(),
3566                                      NumElts);
3567   Index = ModifyToType(Index, WideIndexVT);
3568
3569   SDValue Ops[] = {MSC->getChain(), WideVal, Mask, MSC->getBasePtr(), Index};
3570   return DAG.getMaskedScatter(DAG.getVTList(MVT::Other),
3571                               MSC->getMemoryVT(), dl, Ops,
3572                               MSC->getMemOperand());
3573 }
3574
3575 SDValue DAGTypeLegalizer::WidenVecOp_SETCC(SDNode *N) {
3576   SDValue InOp0 = GetWidenedVector(N->getOperand(0));
3577   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
3578   SDLoc dl(N);
3579
3580   // WARNING: In this code we widen the compare instruction with garbage.
3581   // This garbage may contain denormal floats which may be slow. Is this a real
3582   // concern ? Should we zero the unused lanes if this is a float compare ?
3583
3584   // Get a new SETCC node to compare the newly widened operands.
3585   // Only some of the compared elements are legal.
3586   EVT SVT = TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(),
3587                                    InOp0.getValueType());
3588   SDValue WideSETCC = DAG.getNode(ISD::SETCC, SDLoc(N),
3589                      SVT, InOp0, InOp1, N->getOperand(2));
3590
3591   // Extract the needed results from the result vector.
3592   EVT ResVT = EVT::getVectorVT(*DAG.getContext(),
3593                                SVT.getVectorElementType(),
3594                                N->getValueType(0).getVectorNumElements());
3595   SDValue CC = DAG.getNode(
3596       ISD::EXTRACT_SUBVECTOR, dl, ResVT, WideSETCC,
3597       DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3598
3599   return PromoteTargetBoolean(CC, N->getValueType(0));
3600 }
3601
3602
3603 //===----------------------------------------------------------------------===//
3604 // Vector Widening Utilities
3605 //===----------------------------------------------------------------------===//
3606
3607 // Utility function to find the type to chop up a widen vector for load/store
3608 //  TLI:       Target lowering used to determine legal types.
3609 //  Width:     Width left need to load/store.
3610 //  WidenVT:   The widen vector type to load to/store from
3611 //  Align:     If 0, don't allow use of a wider type
3612 //  WidenEx:   If Align is not 0, the amount additional we can load/store from.
3613
3614 static EVT FindMemType(SelectionDAG& DAG, const TargetLowering &TLI,
3615                        unsigned Width, EVT WidenVT,
3616                        unsigned Align = 0, unsigned WidenEx = 0) {
3617   EVT WidenEltVT = WidenVT.getVectorElementType();
3618   unsigned WidenWidth = WidenVT.getSizeInBits();
3619   unsigned WidenEltWidth = WidenEltVT.getSizeInBits();
3620   unsigned AlignInBits = Align*8;
3621
3622   // If we have one element to load/store, return it.
3623   EVT RetVT = WidenEltVT;
3624   if (Width == WidenEltWidth)
3625     return RetVT;
3626
3627   // See if there is larger legal integer than the element type to load/store.
3628   unsigned VT;
3629   for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE;
3630        VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) {
3631     EVT MemVT((MVT::SimpleValueType) VT);
3632     unsigned MemVTWidth = MemVT.getSizeInBits();
3633     if (MemVT.getSizeInBits() <= WidenEltWidth)
3634       break;
3635     auto Action = TLI.getTypeAction(*DAG.getContext(), MemVT);
3636     if ((Action == TargetLowering::TypeLegal ||
3637          Action == TargetLowering::TypePromoteInteger) &&
3638         (WidenWidth % MemVTWidth) == 0 &&
3639         isPowerOf2_32(WidenWidth / MemVTWidth) &&
3640         (MemVTWidth <= Width ||
3641          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
3642       RetVT = MemVT;
3643       break;
3644     }
3645   }
3646
3647   // See if there is a larger vector type to load/store that has the same vector
3648   // element type and is evenly divisible with the WidenVT.
3649   for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE;
3650        VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) {
3651     EVT MemVT = (MVT::SimpleValueType) VT;
3652     unsigned MemVTWidth = MemVT.getSizeInBits();
3653     if (TLI.isTypeLegal(MemVT) && WidenEltVT == MemVT.getVectorElementType() &&
3654         (WidenWidth % MemVTWidth) == 0 &&
3655         isPowerOf2_32(WidenWidth / MemVTWidth) &&
3656         (MemVTWidth <= Width ||
3657          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
3658       if (RetVT.getSizeInBits() < MemVTWidth || MemVT == WidenVT)
3659         return MemVT;
3660     }
3661   }
3662
3663   return RetVT;
3664 }
3665
3666 // Builds a vector type from scalar loads
3667 //  VecTy: Resulting Vector type
3668 //  LDOps: Load operators to build a vector type
3669 //  [Start,End) the list of loads to use.
3670 static SDValue BuildVectorFromScalar(SelectionDAG& DAG, EVT VecTy,
3671                                      SmallVectorImpl<SDValue> &LdOps,
3672                                      unsigned Start, unsigned End) {
3673   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3674   SDLoc dl(LdOps[Start]);
3675   EVT LdTy = LdOps[Start].getValueType();
3676   unsigned Width = VecTy.getSizeInBits();
3677   unsigned NumElts = Width / LdTy.getSizeInBits();
3678   EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), LdTy, NumElts);
3679
3680   unsigned Idx = 1;
3681   SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT,LdOps[Start]);
3682
3683   for (unsigned i = Start + 1; i != End; ++i) {
3684     EVT NewLdTy = LdOps[i].getValueType();
3685     if (NewLdTy != LdTy) {
3686       NumElts = Width / NewLdTy.getSizeInBits();
3687       NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewLdTy, NumElts);
3688       VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, VecOp);
3689       // Readjust position and vector position based on new load type.
3690       Idx = Idx * LdTy.getSizeInBits() / NewLdTy.getSizeInBits();
3691       LdTy = NewLdTy;
3692     }
3693     VecOp = DAG.getNode(
3694         ISD::INSERT_VECTOR_ELT, dl, NewVecVT, VecOp, LdOps[i],
3695         DAG.getConstant(Idx++, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3696   }
3697   return DAG.getNode(ISD::BITCAST, dl, VecTy, VecOp);
3698 }
3699
3700 SDValue DAGTypeLegalizer::GenWidenVectorLoads(SmallVectorImpl<SDValue> &LdChain,
3701                                               LoadSDNode *LD) {
3702   // The strategy assumes that we can efficiently load power-of-two widths.
3703   // The routine chops the vector into the largest vector loads with the same
3704   // element type or scalar loads and then recombines it to the widen vector
3705   // type.
3706   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
3707   unsigned WidenWidth = WidenVT.getSizeInBits();
3708   EVT LdVT    = LD->getMemoryVT();
3709   SDLoc dl(LD);
3710   assert(LdVT.isVector() && WidenVT.isVector());
3711   assert(LdVT.getVectorElementType() == WidenVT.getVectorElementType());
3712
3713   // Load information
3714   SDValue Chain = LD->getChain();
3715   SDValue BasePtr = LD->getBasePtr();
3716   unsigned Align = LD->getAlignment();
3717   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
3718   AAMDNodes AAInfo = LD->getAAInfo();
3719
3720   int LdWidth = LdVT.getSizeInBits();
3721   int WidthDiff = WidenWidth - LdWidth;
3722   unsigned LdAlign = LD->isVolatile() ? 0 : Align; // Allow wider loads.
3723
3724   // Find the vector type that can load from.
3725   EVT NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
3726   int NewVTWidth = NewVT.getSizeInBits();
3727   SDValue LdOp = DAG.getLoad(NewVT, dl, Chain, BasePtr, LD->getPointerInfo(),
3728                              Align, MMOFlags, AAInfo);
3729   LdChain.push_back(LdOp.getValue(1));
3730
3731   // Check if we can load the element with one instruction.
3732   if (LdWidth <= NewVTWidth) {
3733     if (!NewVT.isVector()) {
3734       unsigned NumElts = WidenWidth / NewVTWidth;
3735       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
3736       SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT, LdOp);
3737       return DAG.getNode(ISD::BITCAST, dl, WidenVT, VecOp);
3738     }
3739     if (NewVT == WidenVT)
3740       return LdOp;
3741
3742     assert(WidenWidth % NewVTWidth == 0);
3743     unsigned NumConcat = WidenWidth / NewVTWidth;
3744     SmallVector<SDValue, 16> ConcatOps(NumConcat);
3745     SDValue UndefVal = DAG.getUNDEF(NewVT);
3746     ConcatOps[0] = LdOp;
3747     for (unsigned i = 1; i != NumConcat; ++i)
3748       ConcatOps[i] = UndefVal;
3749     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, ConcatOps);
3750   }
3751
3752   // Load vector by using multiple loads from largest vector to scalar.
3753   SmallVector<SDValue, 16> LdOps;
3754   LdOps.push_back(LdOp);
3755
3756   LdWidth -= NewVTWidth;
3757   unsigned Offset = 0;
3758
3759   while (LdWidth > 0) {
3760     unsigned Increment = NewVTWidth / 8;
3761     Offset += Increment;
3762     BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
3763                           DAG.getConstant(Increment, dl, BasePtr.getValueType()));
3764
3765     SDValue L;
3766     if (LdWidth < NewVTWidth) {
3767       // The current type we are using is too large. Find a better size.
3768       NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
3769       NewVTWidth = NewVT.getSizeInBits();
3770       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
3771                       LD->getPointerInfo().getWithOffset(Offset),
3772                       MinAlign(Align, Increment), MMOFlags, AAInfo);
3773       LdChain.push_back(L.getValue(1));
3774       if (L->getValueType(0).isVector() && NewVTWidth >= LdWidth) {
3775         // Later code assumes the vector loads produced will be mergeable, so we
3776         // must pad the final entry up to the previous width. Scalars are
3777         // combined separately.
3778         SmallVector<SDValue, 16> Loads;
3779         Loads.push_back(L);
3780         unsigned size = L->getValueSizeInBits(0);
3781         while (size < LdOp->getValueSizeInBits(0)) {
3782           Loads.push_back(DAG.getUNDEF(L->getValueType(0)));
3783           size += L->getValueSizeInBits(0);
3784         }
3785         L = DAG.getNode(ISD::CONCAT_VECTORS, dl, LdOp->getValueType(0), Loads);
3786       }
3787     } else {
3788       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
3789                       LD->getPointerInfo().getWithOffset(Offset),
3790                       MinAlign(Align, Increment), MMOFlags, AAInfo);
3791       LdChain.push_back(L.getValue(1));
3792     }
3793
3794     LdOps.push_back(L);
3795
3796
3797     LdWidth -= NewVTWidth;
3798   }
3799
3800   // Build the vector from the load operations.
3801   unsigned End = LdOps.size();
3802   if (!LdOps[0].getValueType().isVector())
3803     // All the loads are scalar loads.
3804     return BuildVectorFromScalar(DAG, WidenVT, LdOps, 0, End);
3805
3806   // If the load contains vectors, build the vector using concat vector.
3807   // All of the vectors used to load are power-of-2, and the scalar loads can be
3808   // combined to make a power-of-2 vector.
3809   SmallVector<SDValue, 16> ConcatOps(End);
3810   int i = End - 1;
3811   int Idx = End;
3812   EVT LdTy = LdOps[i].getValueType();
3813   // First, combine the scalar loads to a vector.
3814   if (!LdTy.isVector())  {
3815     for (--i; i >= 0; --i) {
3816       LdTy = LdOps[i].getValueType();
3817       if (LdTy.isVector())
3818         break;
3819     }
3820     ConcatOps[--Idx] = BuildVectorFromScalar(DAG, LdTy, LdOps, i + 1, End);
3821   }
3822   ConcatOps[--Idx] = LdOps[i];
3823   for (--i; i >= 0; --i) {
3824     EVT NewLdTy = LdOps[i].getValueType();
3825     if (NewLdTy != LdTy) {
3826       // Create a larger vector.
3827       ConcatOps[End-1] = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewLdTy,
3828                                      makeArrayRef(&ConcatOps[Idx], End - Idx));
3829       Idx = End - 1;
3830       LdTy = NewLdTy;
3831     }
3832     ConcatOps[--Idx] = LdOps[i];
3833   }
3834
3835   if (WidenWidth == LdTy.getSizeInBits() * (End - Idx))
3836     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
3837                        makeArrayRef(&ConcatOps[Idx], End - Idx));
3838
3839   // We need to fill the rest with undefs to build the vector.
3840   unsigned NumOps = WidenWidth / LdTy.getSizeInBits();
3841   SmallVector<SDValue, 16> WidenOps(NumOps);
3842   SDValue UndefVal = DAG.getUNDEF(LdTy);
3843   {
3844     unsigned i = 0;
3845     for (; i != End-Idx; ++i)
3846       WidenOps[i] = ConcatOps[Idx+i];
3847     for (; i != NumOps; ++i)
3848       WidenOps[i] = UndefVal;
3849   }
3850   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, WidenOps);
3851 }
3852
3853 SDValue
3854 DAGTypeLegalizer::GenWidenVectorExtLoads(SmallVectorImpl<SDValue> &LdChain,
3855                                          LoadSDNode *LD,
3856                                          ISD::LoadExtType ExtType) {
3857   // For extension loads, it may not be more efficient to chop up the vector
3858   // and then extend it. Instead, we unroll the load and build a new vector.
3859   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
3860   EVT LdVT    = LD->getMemoryVT();
3861   SDLoc dl(LD);
3862   assert(LdVT.isVector() && WidenVT.isVector());
3863
3864   // Load information
3865   SDValue Chain = LD->getChain();
3866   SDValue BasePtr = LD->getBasePtr();
3867   unsigned Align = LD->getAlignment();
3868   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
3869   AAMDNodes AAInfo = LD->getAAInfo();
3870
3871   EVT EltVT = WidenVT.getVectorElementType();
3872   EVT LdEltVT = LdVT.getVectorElementType();
3873   unsigned NumElts = LdVT.getVectorNumElements();
3874
3875   // Load each element and widen.
3876   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3877   SmallVector<SDValue, 16> Ops(WidenNumElts);
3878   unsigned Increment = LdEltVT.getSizeInBits() / 8;
3879   Ops[0] =
3880       DAG.getExtLoad(ExtType, dl, EltVT, Chain, BasePtr, LD->getPointerInfo(),
3881                      LdEltVT, Align, MMOFlags, AAInfo);
3882   LdChain.push_back(Ops[0].getValue(1));
3883   unsigned i = 0, Offset = Increment;
3884   for (i=1; i < NumElts; ++i, Offset += Increment) {
3885     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
3886                                      BasePtr,
3887                                      DAG.getConstant(Offset, dl,
3888                                                      BasePtr.getValueType()));
3889     Ops[i] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, NewBasePtr,
3890                             LD->getPointerInfo().getWithOffset(Offset), LdEltVT,
3891                             Align, MMOFlags, AAInfo);
3892     LdChain.push_back(Ops[i].getValue(1));
3893   }
3894
3895   // Fill the rest with undefs.
3896   SDValue UndefVal = DAG.getUNDEF(EltVT);
3897   for (; i != WidenNumElts; ++i)
3898     Ops[i] = UndefVal;
3899
3900   return DAG.getBuildVector(WidenVT, dl, Ops);
3901 }
3902
3903 void DAGTypeLegalizer::GenWidenVectorStores(SmallVectorImpl<SDValue> &StChain,
3904                                             StoreSDNode *ST) {
3905   // The strategy assumes that we can efficiently store power-of-two widths.
3906   // The routine chops the vector into the largest vector stores with the same
3907   // element type or scalar stores.
3908   SDValue  Chain = ST->getChain();
3909   SDValue  BasePtr = ST->getBasePtr();
3910   unsigned Align = ST->getAlignment();
3911   MachineMemOperand::Flags MMOFlags = ST->getMemOperand()->getFlags();
3912   AAMDNodes AAInfo = ST->getAAInfo();
3913   SDValue  ValOp = GetWidenedVector(ST->getValue());
3914   SDLoc dl(ST);
3915
3916   EVT StVT = ST->getMemoryVT();
3917   unsigned StWidth = StVT.getSizeInBits();
3918   EVT ValVT = ValOp.getValueType();
3919   unsigned ValWidth = ValVT.getSizeInBits();
3920   EVT ValEltVT = ValVT.getVectorElementType();
3921   unsigned ValEltWidth = ValEltVT.getSizeInBits();
3922   assert(StVT.getVectorElementType() == ValEltVT);
3923
3924   int Idx = 0;          // current index to store
3925   unsigned Offset = 0;  // offset from base to store
3926   while (StWidth != 0) {
3927     // Find the largest vector type we can store with.
3928     EVT NewVT = FindMemType(DAG, TLI, StWidth, ValVT);
3929     unsigned NewVTWidth = NewVT.getSizeInBits();
3930     unsigned Increment = NewVTWidth / 8;
3931     if (NewVT.isVector()) {
3932       unsigned NumVTElts = NewVT.getVectorNumElements();
3933       do {
3934         SDValue EOp = DAG.getNode(
3935             ISD::EXTRACT_SUBVECTOR, dl, NewVT, ValOp,
3936             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3937         StChain.push_back(DAG.getStore(
3938             Chain, dl, EOp, BasePtr, ST->getPointerInfo().getWithOffset(Offset),
3939             MinAlign(Align, Offset), MMOFlags, AAInfo));
3940         StWidth -= NewVTWidth;
3941         Offset += Increment;
3942         Idx += NumVTElts;
3943         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
3944                               DAG.getConstant(Increment, dl,
3945                                               BasePtr.getValueType()));
3946       } while (StWidth != 0 && StWidth >= NewVTWidth);
3947     } else {
3948       // Cast the vector to the scalar type we can store.
3949       unsigned NumElts = ValWidth / NewVTWidth;
3950       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
3951       SDValue VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, ValOp);
3952       // Readjust index position based on new vector type.
3953       Idx = Idx * ValEltWidth / NewVTWidth;
3954       do {
3955         SDValue EOp = DAG.getNode(
3956             ISD::EXTRACT_VECTOR_ELT, dl, NewVT, VecOp,
3957             DAG.getConstant(Idx++, dl,
3958                             TLI.getVectorIdxTy(DAG.getDataLayout())));
3959         StChain.push_back(DAG.getStore(
3960             Chain, dl, EOp, BasePtr, ST->getPointerInfo().getWithOffset(Offset),
3961             MinAlign(Align, Offset), MMOFlags, AAInfo));
3962         StWidth -= NewVTWidth;
3963         Offset += Increment;
3964         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
3965                               DAG.getConstant(Increment, dl,
3966                                               BasePtr.getValueType()));
3967       } while (StWidth != 0 && StWidth >= NewVTWidth);
3968       // Restore index back to be relative to the original widen element type.
3969       Idx = Idx * NewVTWidth / ValEltWidth;
3970     }
3971   }
3972 }
3973
3974 void
3975 DAGTypeLegalizer::GenWidenVectorTruncStores(SmallVectorImpl<SDValue> &StChain,
3976                                             StoreSDNode *ST) {
3977   // For extension loads, it may not be more efficient to truncate the vector
3978   // and then store it. Instead, we extract each element and then store it.
3979   SDValue Chain = ST->getChain();
3980   SDValue BasePtr = ST->getBasePtr();
3981   unsigned Align = ST->getAlignment();
3982   MachineMemOperand::Flags MMOFlags = ST->getMemOperand()->getFlags();
3983   AAMDNodes AAInfo = ST->getAAInfo();
3984   SDValue ValOp = GetWidenedVector(ST->getValue());
3985   SDLoc dl(ST);
3986
3987   EVT StVT = ST->getMemoryVT();
3988   EVT ValVT = ValOp.getValueType();
3989
3990   // It must be true that the wide vector type is bigger than where we need to
3991   // store.
3992   assert(StVT.isVector() && ValOp.getValueType().isVector());
3993   assert(StVT.bitsLT(ValOp.getValueType()));
3994
3995   // For truncating stores, we can not play the tricks of chopping legal vector
3996   // types and bitcast it to the right type. Instead, we unroll the store.
3997   EVT StEltVT  = StVT.getVectorElementType();
3998   EVT ValEltVT = ValVT.getVectorElementType();
3999   unsigned Increment = ValEltVT.getSizeInBits() / 8;
4000   unsigned NumElts = StVT.getVectorNumElements();
4001   SDValue EOp = DAG.getNode(
4002       ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
4003       DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4004   StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, BasePtr,
4005                                       ST->getPointerInfo(), StEltVT, Align,
4006                                       MMOFlags, AAInfo));
4007   unsigned Offset = Increment;
4008   for (unsigned i=1; i < NumElts; ++i, Offset += Increment) {
4009     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
4010                                      BasePtr,
4011                                      DAG.getConstant(Offset, dl,
4012                                                      BasePtr.getValueType()));
4013     SDValue EOp = DAG.getNode(
4014         ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
4015         DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4016     StChain.push_back(DAG.getTruncStore(
4017         Chain, dl, EOp, NewBasePtr, ST->getPointerInfo().getWithOffset(Offset),
4018         StEltVT, MinAlign(Align, Offset), MMOFlags, AAInfo));
4019   }
4020 }
4021
4022 /// Modifies a vector input (widen or narrows) to a vector of NVT.  The
4023 /// input vector must have the same element type as NVT.
4024 /// FillWithZeroes specifies that the vector should be widened with zeroes.
4025 SDValue DAGTypeLegalizer::ModifyToType(SDValue InOp, EVT NVT,
4026                                        bool FillWithZeroes) {
4027   // Note that InOp might have been widened so it might already have
4028   // the right width or it might need be narrowed.
4029   EVT InVT = InOp.getValueType();
4030   assert(InVT.getVectorElementType() == NVT.getVectorElementType() &&
4031          "input and widen element type must match");
4032   SDLoc dl(InOp);
4033
4034   // Check if InOp already has the right width.
4035   if (InVT == NVT)
4036     return InOp;
4037
4038   unsigned InNumElts = InVT.getVectorNumElements();
4039   unsigned WidenNumElts = NVT.getVectorNumElements();
4040   if (WidenNumElts > InNumElts && WidenNumElts % InNumElts == 0) {
4041     unsigned NumConcat = WidenNumElts / InNumElts;
4042     SmallVector<SDValue, 16> Ops(NumConcat);
4043     SDValue FillVal = FillWithZeroes ? DAG.getConstant(0, dl, InVT) :
4044       DAG.getUNDEF(InVT);
4045     Ops[0] = InOp;
4046     for (unsigned i = 1; i != NumConcat; ++i)
4047       Ops[i] = FillVal;
4048
4049     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, Ops);
4050   }
4051
4052   if (WidenNumElts < InNumElts && InNumElts % WidenNumElts)
4053     return DAG.getNode(
4054         ISD::EXTRACT_SUBVECTOR, dl, NVT, InOp,
4055         DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4056
4057   // Fall back to extract and build.
4058   SmallVector<SDValue, 16> Ops(WidenNumElts);
4059   EVT EltVT = NVT.getVectorElementType();
4060   unsigned MinNumElts = std::min(WidenNumElts, InNumElts);
4061   unsigned Idx;
4062   for (Idx = 0; Idx < MinNumElts; ++Idx)
4063     Ops[Idx] = DAG.getNode(
4064         ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
4065         DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4066
4067   SDValue FillVal = FillWithZeroes ? DAG.getConstant(0, dl, EltVT) :
4068     DAG.getUNDEF(EltVT);
4069   for ( ; Idx < WidenNumElts; ++Idx)
4070     Ops[Idx] = FillVal;
4071   return DAG.getBuildVector(NVT, dl, Ops);
4072 }