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