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