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