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