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 //===----------------------------------------------------------------------===//
  30 //  Result Vector Scalarization: <1 x ty> -> ty.
  31 //===----------------------------------------------------------------------===//
  32
  33 void DAGTypeLegalizer::ScalarizeVectorResult(SDNode *N, unsigned ResNo) {
  34   DEBUG(dbgs() << "Scalarize node result " << ResNo << ": ";
  35         N->dump(&DAG);
  36         dbgs() << "\n");
  37   SDValue R = SDValue();
  38
  39   switch (N->getOpcode()) {
  40   default:
  41 #ifndef NDEBUG
  42     dbgs() << "ScalarizeVectorResult #" << ResNo << ": ";
  43     N->dump(&DAG);
  44     dbgs() << "\n";
  45 #endif
  46     report_fatal_error("Do not know how to scalarize the result of this "
  47                        "operator!\n");
  48
  49   case ISD::MERGE_VALUES:      R = ScalarizeVecRes_MERGE_VALUES(N, ResNo);break;
  50   case ISD::BITCAST:           R = ScalarizeVecRes_BITCAST(N); break;
  51   case ISD::BUILD_VECTOR:      R = ScalarizeVecRes_BUILD_VECTOR(N); break;
  52   case ISD::CONVERT_RNDSAT:    R = ScalarizeVecRes_CONVERT_RNDSAT(N); break;
  53   case ISD::EXTRACT_SUBVECTOR: R = ScalarizeVecRes_EXTRACT_SUBVECTOR(N); break;
  54   case ISD::FP_ROUND:          R = ScalarizeVecRes_FP_ROUND(N); break;
  55   case ISD::FP_ROUND_INREG:    R = ScalarizeVecRes_InregOp(N); break;
  56   case ISD::FPOWI:             R = ScalarizeVecRes_FPOWI(N); break;
  57   case ISD::INSERT_VECTOR_ELT: R = ScalarizeVecRes_INSERT_VECTOR_ELT(N); break;
  58   case ISD::LOAD:           R = ScalarizeVecRes_LOAD(cast<LoadSDNode>(N));break;
  59   case ISD::SCALAR_TO_VECTOR:  R = ScalarizeVecRes_SCALAR_TO_VECTOR(N); break;
  60   case ISD::SIGN_EXTEND_INREG: R = ScalarizeVecRes_InregOp(N); break;
  61   case ISD::VSELECT:           R = ScalarizeVecRes_VSELECT(N); break;
  62   case ISD::SELECT:            R = ScalarizeVecRes_SELECT(N); break;
  63   case ISD::SELECT_CC:         R = ScalarizeVecRes_SELECT_CC(N); break;
  64   case ISD::SETCC:             R = ScalarizeVecRes_SETCC(N); break;
  65   case ISD::UNDEF:             R = ScalarizeVecRes_UNDEF(N); break;
  66   case ISD::VECTOR_SHUFFLE:    R = ScalarizeVecRes_VECTOR_SHUFFLE(N); break;
  67   case ISD::ANY_EXTEND:
  68   case ISD::CTLZ:
  69   case ISD::CTPOP:
  70   case ISD::CTTZ:
  71   case ISD::FABS:
  72   case ISD::FCEIL:
  73   case ISD::FCOS:
  74   case ISD::FEXP:
  75   case ISD::FEXP2:
  76   case ISD::FFLOOR:
  77   case ISD::FLOG:
  78   case ISD::FLOG10:
  79   case ISD::FLOG2:
  80   case ISD::FNEARBYINT:
  81   case ISD::FNEG:
  82   case ISD::FP_EXTEND:
  83   case ISD::FP_TO_SINT:
  84   case ISD::FP_TO_UINT:
  85   case ISD::FRINT:
  86   case ISD::FSIN:
  87   case ISD::FSQRT:
  88   case ISD::FTRUNC:
  89   case ISD::SIGN_EXTEND:
  90   case ISD::SINT_TO_FP:
  91   case ISD::TRUNCATE:
  92   case ISD::UINT_TO_FP:
  93   case ISD::ZERO_EXTEND:
  94     R = ScalarizeVecRes_UnaryOp(N);
  95     break;
  96
  97   case ISD::ADD:
  98   case ISD::AND:
  99   case ISD::FADD:
 100   case ISD::FDIV:
 101   case ISD::FMUL:
 102   case ISD::FPOW:
 103   case ISD::FREM:
 104   case ISD::FSUB:
 105   case ISD::MUL:
 106   case ISD::OR:
 107   case ISD::SDIV:
 108   case ISD::SREM:
 109   case ISD::SUB:
 110   case ISD::UDIV:
 111   case ISD::UREM:
 112   case ISD::XOR:
 113   case ISD::SHL:
 114   case ISD::SRA:
 115   case ISD::SRL:
 116     R = ScalarizeVecRes_BinOp(N);
 117     break;
 118   case ISD::FMA:
 119     R = ScalarizeVecRes_TernaryOp(N);
 120     break;
 121   }
 122
 123   // If R is null, the sub-method took care of registering the result.
 124   if (R.getNode())
 125     SetScalarizedVector(SDValue(N, ResNo), R);
 126 }
 127
 128 SDValue DAGTypeLegalizer::ScalarizeVecRes_BinOp(SDNode *N) {
 129   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 130   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 131   return DAG.getNode(N->getOpcode(), SDLoc(N),
 132                      LHS.getValueType(), LHS, RHS);
 133 }
 134
 135 SDValue DAGTypeLegalizer::ScalarizeVecRes_TernaryOp(SDNode *N) {
 136   SDValue Op0 = GetScalarizedVector(N->getOperand(0));
 137   SDValue Op1 = GetScalarizedVector(N->getOperand(1));
 138   SDValue Op2 = GetScalarizedVector(N->getOperand(2));
 139   return DAG.getNode(N->getOpcode(), SDLoc(N),
 140                      Op0.getValueType(), Op0, Op1, Op2);
 141 }
 142
 143 SDValue DAGTypeLegalizer::ScalarizeVecRes_MERGE_VALUES(SDNode *N,
 144                                                        unsigned ResNo) {
 145   SDValue Op = DisintegrateMERGE_VALUES(N, ResNo);
 146   return GetScalarizedVector(Op);
 147 }
 148
 149 SDValue DAGTypeLegalizer::ScalarizeVecRes_BITCAST(SDNode *N) {
 150   EVT NewVT = N->getValueType(0).getVectorElementType();
 151   return DAG.getNode(ISD::BITCAST, SDLoc(N),
 152                      NewVT, N->getOperand(0));
 153 }
 154
 155 SDValue DAGTypeLegalizer::ScalarizeVecRes_BUILD_VECTOR(SDNode *N) {
 156   EVT EltVT = N->getValueType(0).getVectorElementType();
 157   SDValue InOp = N->getOperand(0);
 158   // The BUILD_VECTOR operands may be of wider element types and
 159   // we may need to truncate them back to the requested return type.
 160   if (EltVT.isInteger())
 161     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
 162   return InOp;
 163 }
 164
 165 SDValue DAGTypeLegalizer::ScalarizeVecRes_CONVERT_RNDSAT(SDNode *N) {
 166   EVT NewVT = N->getValueType(0).getVectorElementType();
 167   SDValue Op0 = GetScalarizedVector(N->getOperand(0));
 168   return DAG.getConvertRndSat(NewVT, SDLoc(N),
 169                               Op0, DAG.getValueType(NewVT),
 170                               DAG.getValueType(Op0.getValueType()),
 171                               N->getOperand(3),
 172                               N->getOperand(4),
 173                               cast<CvtRndSatSDNode>(N)->getCvtCode());
 174 }
 175
 176 SDValue DAGTypeLegalizer::ScalarizeVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
 177   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
 178                      N->getValueType(0).getVectorElementType(),
 179                      N->getOperand(0), N->getOperand(1));
 180 }
 181
 182 SDValue DAGTypeLegalizer::ScalarizeVecRes_FP_ROUND(SDNode *N) {
 183   EVT NewVT = N->getValueType(0).getVectorElementType();
 184   SDValue Op = GetScalarizedVector(N->getOperand(0));
 185   return DAG.getNode(ISD::FP_ROUND, SDLoc(N),
 186                      NewVT, Op, N->getOperand(1));
 187 }
 188
 189 SDValue DAGTypeLegalizer::ScalarizeVecRes_FPOWI(SDNode *N) {
 190   SDValue Op = GetScalarizedVector(N->getOperand(0));
 191   return DAG.getNode(ISD::FPOWI, SDLoc(N),
 192                      Op.getValueType(), Op, N->getOperand(1));
 193 }
 194
 195 SDValue DAGTypeLegalizer::ScalarizeVecRes_INSERT_VECTOR_ELT(SDNode *N) {
 196   // The value to insert may have a wider type than the vector element type,
 197   // so be sure to truncate it to the element type if necessary.
 198   SDValue Op = N->getOperand(1);
 199   EVT EltVT = N->getValueType(0).getVectorElementType();
 200   if (Op.getValueType() != EltVT)
 201     // FIXME: Can this happen for floating point types?
 202     Op = DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, Op);
 203   return Op;
 204 }
 205
 206 SDValue DAGTypeLegalizer::ScalarizeVecRes_LOAD(LoadSDNode *N) {
 207   assert(N->isUnindexed() && "Indexed vector load?");
 208
 209   SDValue Result = DAG.getLoad(ISD::UNINDEXED,
 210                                N->getExtensionType(),
 211                                N->getValueType(0).getVectorElementType(),
 212                                SDLoc(N),
 213                                N->getChain(), N->getBasePtr(),
 214                                DAG.getUNDEF(N->getBasePtr().getValueType()),
 215                                N->getPointerInfo(),
 216                                N->getMemoryVT().getVectorElementType(),
 217                                N->isVolatile(), N->isNonTemporal(),
 218                                N->isInvariant(), N->getOriginalAlignment());
 219
 220   // Legalized the chain result - switch anything that used the old chain to
 221   // use the new one.
 222   ReplaceValueWith(SDValue(N, 1), Result.getValue(1));
 223   return Result;
 224 }
 225
 226 SDValue DAGTypeLegalizer::ScalarizeVecRes_UnaryOp(SDNode *N) {
 227   // Get the dest type - it doesn't always match the input type, e.g. int_to_fp.
 228   EVT DestVT = N->getValueType(0).getVectorElementType();
 229   SDValue Op = GetScalarizedVector(N->getOperand(0));
 230   return DAG.getNode(N->getOpcode(), SDLoc(N), DestVT, Op);
 231 }
 232
 233 SDValue DAGTypeLegalizer::ScalarizeVecRes_InregOp(SDNode *N) {
 234   EVT EltVT = N->getValueType(0).getVectorElementType();
 235   EVT ExtVT = cast<VTSDNode>(N->getOperand(1))->getVT().getVectorElementType();
 236   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 237   return DAG.getNode(N->getOpcode(), SDLoc(N), EltVT,
 238                      LHS, DAG.getValueType(ExtVT));
 239 }
 240
 241 SDValue DAGTypeLegalizer::ScalarizeVecRes_SCALAR_TO_VECTOR(SDNode *N) {
 242   // If the operand is wider than the vector element type then it is implicitly
 243   // truncated.  Make that explicit here.
 244   EVT EltVT = N->getValueType(0).getVectorElementType();
 245   SDValue InOp = N->getOperand(0);
 246   if (InOp.getValueType() != EltVT)
 247     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
 248   return InOp;
 249 }
 250
 251 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSELECT(SDNode *N) {
 252   SDValue Cond = GetScalarizedVector(N->getOperand(0));
 253   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 254   TargetLowering::BooleanContent ScalarBool = TLI.getBooleanContents(false);
 255   TargetLowering::BooleanContent VecBool = TLI.getBooleanContents(true);
 256   if (ScalarBool != VecBool) {
 257     EVT CondVT = Cond.getValueType();
 258     switch (ScalarBool) {
 259       case TargetLowering::UndefinedBooleanContent:
 260         break;
 261       case TargetLowering::ZeroOrOneBooleanContent:
 262         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
 263                VecBool == TargetLowering::ZeroOrNegativeOneBooleanContent);
 264         // Vector read from all ones, scalar expects a single 1 so mask.
 265         Cond = DAG.getNode(ISD::AND, SDLoc(N), CondVT,
 266                            Cond, DAG.getConstant(1, CondVT));
 267         break;
 268       case TargetLowering::ZeroOrNegativeOneBooleanContent:
 269         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
 270                VecBool == TargetLowering::ZeroOrOneBooleanContent);
 271         // Vector reads from a one, scalar from all ones so sign extend.
 272         Cond = DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N), CondVT,
 273                            Cond, DAG.getValueType(MVT::i1));
 274         break;
 275     }
 276   }
 277
 278   return DAG.getSelect(SDLoc(N),
 279                        LHS.getValueType(), Cond, LHS,
 280                        GetScalarizedVector(N->getOperand(2)));
 281 }
 282
 283 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT(SDNode *N) {
 284   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 285   return DAG.getSelect(SDLoc(N),
 286                        LHS.getValueType(), N->getOperand(0), LHS,
 287                        GetScalarizedVector(N->getOperand(2)));
 288 }
 289
 290 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT_CC(SDNode *N) {
 291   SDValue LHS = GetScalarizedVector(N->getOperand(2));
 292   return DAG.getNode(ISD::SELECT_CC, SDLoc(N), LHS.getValueType(),
 293                      N->getOperand(0), N->getOperand(1),
 294                      LHS, GetScalarizedVector(N->getOperand(3)),
 295                      N->getOperand(4));
 296 }
 297
 298 SDValue DAGTypeLegalizer::ScalarizeVecRes_SETCC(SDNode *N) {
 299   assert(N->getValueType(0).isVector() ==
 300          N->getOperand(0).getValueType().isVector() &&
 301          "Scalar/Vector type mismatch");
 302
 303   if (N->getValueType(0).isVector()) return ScalarizeVecRes_VSETCC(N);
 304
 305   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 306   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 307   SDLoc DL(N);
 308
 309   // Turn it into a scalar SETCC.
 310   return DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS, N->getOperand(2));
 311 }
 312
 313 SDValue DAGTypeLegalizer::ScalarizeVecRes_UNDEF(SDNode *N) {
 314   return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
 315 }
 316
 317 SDValue DAGTypeLegalizer::ScalarizeVecRes_VECTOR_SHUFFLE(SDNode *N) {
 318   // Figure out if the scalar is the LHS or RHS and return it.
 319   SDValue Arg = N->getOperand(2).getOperand(0);
 320   if (Arg.getOpcode() == ISD::UNDEF)
 321     return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
 322   unsigned Op = !cast<ConstantSDNode>(Arg)->isNullValue();
 323   return GetScalarizedVector(N->getOperand(Op));
 324 }
 325
 326 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSETCC(SDNode *N) {
 327   assert(N->getValueType(0).isVector() &&
 328          N->getOperand(0).getValueType().isVector() &&
 329          "Operand types must be vectors");
 330
 331   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 332   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 333   EVT NVT = N->getValueType(0).getVectorElementType();
 334   SDLoc DL(N);
 335
 336   // Turn it into a scalar SETCC.
 337   SDValue Res = DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS,
 338                             N->getOperand(2));
 339   // Vectors may have a different boolean contents to scalars.  Promote the
 340   // value appropriately.
 341   ISD::NodeType ExtendCode =
 342     TargetLowering::getExtendForContent(TLI.getBooleanContents(true));
 343   return DAG.getNode(ExtendCode, DL, NVT, Res);
 344 }
 345
 346
 347 //===----------------------------------------------------------------------===//
 348 //  Operand Vector Scalarization <1 x ty> -> ty.
 349 //===----------------------------------------------------------------------===//
 350
 351 bool DAGTypeLegalizer::ScalarizeVectorOperand(SDNode *N, unsigned OpNo) {
 352   DEBUG(dbgs() << "Scalarize node operand " << OpNo << ": ";
 353         N->dump(&DAG);
 354         dbgs() << "\n");
 355   SDValue Res = SDValue();
 356
 357   if (Res.getNode() == 0) {
 358     switch (N->getOpcode()) {
 359     default:
 360 #ifndef NDEBUG
 361       dbgs() << "ScalarizeVectorOperand Op #" << OpNo << ": ";
 362       N->dump(&DAG);
 363       dbgs() << "\n";
 364 #endif
 365       llvm_unreachable("Do not know how to scalarize this operator's operand!");
 366     case ISD::BITCAST:
 367       Res = ScalarizeVecOp_BITCAST(N);
 368       break;
 369     case ISD::ANY_EXTEND:
 370     case ISD::ZERO_EXTEND:
 371     case ISD::SIGN_EXTEND:
 372       Res = ScalarizeVecOp_EXTEND(N);
 373       break;
 374     case ISD::CONCAT_VECTORS:
 375       Res = ScalarizeVecOp_CONCAT_VECTORS(N);
 376       break;
 377     case ISD::EXTRACT_VECTOR_ELT:
 378       Res = ScalarizeVecOp_EXTRACT_VECTOR_ELT(N);
 379       break;
 380     case ISD::STORE:
 381       Res = ScalarizeVecOp_STORE(cast<StoreSDNode>(N), OpNo);
 382       break;
 383     }
 384   }
 385
 386   // If the result is null, the sub-method took care of registering results etc.
 387   if (!Res.getNode()) return false;
 388
 389   // If the result is N, the sub-method updated N in place.  Tell the legalizer
 390   // core about this.
 391   if (Res.getNode() == N)
 392     return true;
 393
 394   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 395          "Invalid operand expansion");
 396
 397   ReplaceValueWith(SDValue(N, 0), Res);
 398   return false;
 399 }
 400
 401 /// ScalarizeVecOp_BITCAST - If the value to convert is a vector that needs
 402 /// to be scalarized, it must be <1 x ty>.  Convert the element instead.
 403 SDValue DAGTypeLegalizer::ScalarizeVecOp_BITCAST(SDNode *N) {
 404   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 405   return DAG.getNode(ISD::BITCAST, SDLoc(N),
 406                      N->getValueType(0), Elt);
 407 }
 408
 409 /// ScalarizeVecOp_EXTEND - If the value to extend is a vector that needs
 410 /// to be scalarized, it must be <1 x ty>.  Extend the element instead.
 411 SDValue DAGTypeLegalizer::ScalarizeVecOp_EXTEND(SDNode *N) {
 412   assert(N->getValueType(0).getVectorNumElements() == 1 &&
 413          "Unexected vector type!");
 414   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 415   SmallVector<SDValue, 1> Ops(1);
 416   Ops[0] = DAG.getNode(N->getOpcode(), SDLoc(N),
 417                        N->getValueType(0).getScalarType(), Elt);
 418   // Revectorize the result so the types line up with what the uses of this
 419   // expression expect.
 420   return DAG.getNode(ISD::BUILD_VECTOR, SDLoc(N), N->getValueType(0),
 421                      &Ops[0], 1);
 422 }
 423
 424 /// ScalarizeVecOp_CONCAT_VECTORS - The vectors to concatenate have length one -
 425 /// use a BUILD_VECTOR instead.
 426 SDValue DAGTypeLegalizer::ScalarizeVecOp_CONCAT_VECTORS(SDNode *N) {
 427   SmallVector<SDValue, 8> Ops(N->getNumOperands());
 428   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i)
 429     Ops[i] = GetScalarizedVector(N->getOperand(i));
 430   return DAG.getNode(ISD::BUILD_VECTOR, SDLoc(N), N->getValueType(0),
 431                      &Ops[0], Ops.size());
 432 }
 433
 434 /// ScalarizeVecOp_EXTRACT_VECTOR_ELT - If the input is a vector that needs to
 435 /// be scalarized, it must be <1 x ty>, so just return the element, ignoring the
 436 /// index.
 437 SDValue DAGTypeLegalizer::ScalarizeVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
 438   SDValue Res = GetScalarizedVector(N->getOperand(0));
 439   if (Res.getValueType() != N->getValueType(0))
 440     Res = DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), N->getValueType(0),
 441                       Res);
 442   return Res;
 443 }
 444
 445 /// ScalarizeVecOp_STORE - If the value to store is a vector that needs to be
 446 /// scalarized, it must be <1 x ty>.  Just store the element.
 447 SDValue DAGTypeLegalizer::ScalarizeVecOp_STORE(StoreSDNode *N, unsigned OpNo){
 448   assert(N->isUnindexed() && "Indexed store of one-element vector?");
 449   assert(OpNo == 1 && "Do not know how to scalarize this operand!");
 450   SDLoc dl(N);
 451
 452   if (N->isTruncatingStore())
 453     return DAG.getTruncStore(N->getChain(), dl,
 454                              GetScalarizedVector(N->getOperand(1)),
 455                              N->getBasePtr(), N->getPointerInfo(),
 456                              N->getMemoryVT().getVectorElementType(),
 457                              N->isVolatile(), N->isNonTemporal(),
 458                              N->getAlignment());
 459
 460   return DAG.getStore(N->getChain(), dl, GetScalarizedVector(N->getOperand(1)),
 461                       N->getBasePtr(), N->getPointerInfo(),
 462                       N->isVolatile(), N->isNonTemporal(),
 463                       N->getOriginalAlignment());
 464 }
 465
 466
 467 //===----------------------------------------------------------------------===//
 468 //  Result Vector Splitting
 469 //===----------------------------------------------------------------------===//
 470
 471 /// SplitVectorResult - This method is called when the specified result of the
 472 /// specified node is found to need vector splitting.  At this point, the node
 473 /// may also have invalid operands or may have other results that need
 474 /// legalization, we just know that (at least) one result needs vector
 475 /// splitting.
 476 void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) {
 477   DEBUG(dbgs() << "Split node result: ";
 478         N->dump(&DAG);
 479         dbgs() << "\n");
 480   SDValue Lo, Hi;
 481
 482   // See if the target wants to custom expand this node.
 483   if (CustomLowerNode(N, N->getValueType(ResNo), true))
 484     return;
 485
 486   switch (N->getOpcode()) {
 487   default:
 488 #ifndef NDEBUG
 489     dbgs() << "SplitVectorResult #" << ResNo << ": ";
 490     N->dump(&DAG);
 491     dbgs() << "\n";
 492 #endif
 493     report_fatal_error("Do not know how to split the result of this "
 494                        "operator!\n");
 495
 496   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, ResNo, Lo, Hi); break;
 497   case ISD::VSELECT:
 498   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
 499   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
 500   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
 501   case ISD::BITCAST:           SplitVecRes_BITCAST(N, Lo, Hi); break;
 502   case ISD::BUILD_VECTOR:      SplitVecRes_BUILD_VECTOR(N, Lo, Hi); break;
 503   case ISD::CONCAT_VECTORS:    SplitVecRes_CONCAT_VECTORS(N, Lo, Hi); break;
 504   case ISD::EXTRACT_SUBVECTOR: SplitVecRes_EXTRACT_SUBVECTOR(N, Lo, Hi); break;
 505   case ISD::FP_ROUND_INREG:    SplitVecRes_InregOp(N, Lo, Hi); break;
 506   case ISD::FPOWI:             SplitVecRes_FPOWI(N, Lo, Hi); break;
 507   case ISD::INSERT_VECTOR_ELT: SplitVecRes_INSERT_VECTOR_ELT(N, Lo, Hi); break;
 508   case ISD::SCALAR_TO_VECTOR:  SplitVecRes_SCALAR_TO_VECTOR(N, Lo, Hi); break;
 509   case ISD::SIGN_EXTEND_INREG: SplitVecRes_InregOp(N, Lo, Hi); break;
 510   case ISD::LOAD:
 511     SplitVecRes_LOAD(cast<LoadSDNode>(N), Lo, Hi);
 512     break;
 513   case ISD::SETCC:
 514     SplitVecRes_SETCC(N, Lo, Hi);
 515     break;
 516   case ISD::VECTOR_SHUFFLE:
 517     SplitVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N), Lo, Hi);
 518     break;
 519
 520   case ISD::ANY_EXTEND:
 521   case ISD::CONVERT_RNDSAT:
 522   case ISD::CTLZ:
 523   case ISD::CTTZ:
 524   case ISD::CTLZ_ZERO_UNDEF:
 525   case ISD::CTTZ_ZERO_UNDEF:
 526   case ISD::CTPOP:
 527   case ISD::FABS:
 528   case ISD::FCEIL:
 529   case ISD::FCOS:
 530   case ISD::FEXP:
 531   case ISD::FEXP2:
 532   case ISD::FFLOOR:
 533   case ISD::FLOG:
 534   case ISD::FLOG10:
 535   case ISD::FLOG2:
 536   case ISD::FNEARBYINT:
 537   case ISD::FNEG:
 538   case ISD::FP_EXTEND:
 539   case ISD::FP_ROUND:
 540   case ISD::FP_TO_SINT:
 541   case ISD::FP_TO_UINT:
 542   case ISD::FRINT:
 543   case ISD::FSIN:
 544   case ISD::FSQRT:
 545   case ISD::FTRUNC:
 546   case ISD::SIGN_EXTEND:
 547   case ISD::SINT_TO_FP:
 548   case ISD::TRUNCATE:
 549   case ISD::UINT_TO_FP:
 550   case ISD::ZERO_EXTEND:
 551     SplitVecRes_UnaryOp(N, Lo, Hi);
 552     break;
 553
 554   case ISD::ADD:
 555   case ISD::SUB:
 556   case ISD::MUL:
 557   case ISD::FADD:
 558   case ISD::FSUB:
 559   case ISD::FMUL:
 560   case ISD::SDIV:
 561   case ISD::UDIV:
 562   case ISD::FDIV:
 563   case ISD::FPOW:
 564   case ISD::AND:
 565   case ISD::OR:
 566   case ISD::XOR:
 567   case ISD::SHL:
 568   case ISD::SRA:
 569   case ISD::SRL:
 570   case ISD::UREM:
 571   case ISD::SREM:
 572   case ISD::FREM:
 573     SplitVecRes_BinOp(N, Lo, Hi);
 574     break;
 575   case ISD::FMA:
 576     SplitVecRes_TernaryOp(N, Lo, Hi);
 577     break;
 578   }
 579
 580   // If Lo/Hi is null, the sub-method took care of registering results etc.
 581   if (Lo.getNode())
 582     SetSplitVector(SDValue(N, ResNo), Lo, Hi);
 583 }
 584
 585 void DAGTypeLegalizer::SplitVecRes_BinOp(SDNode *N, SDValue &Lo,
 586                                          SDValue &Hi) {
 587   SDValue LHSLo, LHSHi;
 588   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 589   SDValue RHSLo, RHSHi;
 590   GetSplitVector(N->getOperand(1), RHSLo, RHSHi);
 591   SDLoc dl(N);
 592
 593   Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo, RHSLo);
 594   Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi, RHSHi);
 595 }
 596
 597 void DAGTypeLegalizer::SplitVecRes_TernaryOp(SDNode *N, SDValue &Lo,
 598                                              SDValue &Hi) {
 599   SDValue Op0Lo, Op0Hi;
 600   GetSplitVector(N->getOperand(0), Op0Lo, Op0Hi);
 601   SDValue Op1Lo, Op1Hi;
 602   GetSplitVector(N->getOperand(1), Op1Lo, Op1Hi);
 603   SDValue Op2Lo, Op2Hi;
 604   GetSplitVector(N->getOperand(2), Op2Lo, Op2Hi);
 605   SDLoc dl(N);
 606
 607   Lo = DAG.getNode(N->getOpcode(), dl, Op0Lo.getValueType(),
 608                    Op0Lo, Op1Lo, Op2Lo);
 609   Hi = DAG.getNode(N->getOpcode(), dl, Op0Hi.getValueType(),
 610                    Op0Hi, Op1Hi, Op2Hi);
 611 }
 612
 613 void DAGTypeLegalizer::SplitVecRes_BITCAST(SDNode *N, SDValue &Lo,
 614                                            SDValue &Hi) {
 615   // We know the result is a vector.  The input may be either a vector or a
 616   // scalar value.
 617   EVT LoVT, HiVT;
 618   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 619   SDLoc dl(N);
 620
 621   SDValue InOp = N->getOperand(0);
 622   EVT InVT = InOp.getValueType();
 623
 624   // Handle some special cases efficiently.
 625   switch (getTypeAction(InVT)) {
 626   case TargetLowering::TypeLegal:
 627   case TargetLowering::TypePromoteInteger:
 628   case TargetLowering::TypeSoftenFloat:
 629   case TargetLowering::TypeScalarizeVector:
 630   case TargetLowering::TypeWidenVector:
 631     break;
 632   case TargetLowering::TypeExpandInteger:
 633   case TargetLowering::TypeExpandFloat:
 634     // A scalar to vector conversion, where the scalar needs expansion.
 635     // If the vector is being split in two then we can just convert the
 636     // expanded pieces.
 637     if (LoVT == HiVT) {
 638       GetExpandedOp(InOp, Lo, Hi);
 639       if (TLI.isBigEndian())
 640         std::swap(Lo, Hi);
 641       Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 642       Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 643       return;
 644     }
 645     break;
 646   case TargetLowering::TypeSplitVector:
 647     // If the input is a vector that needs to be split, convert each split
 648     // piece of the input now.
 649     GetSplitVector(InOp, Lo, Hi);
 650     Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 651     Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 652     return;
 653   }
 654
 655   // In the general case, convert the input to an integer and split it by hand.
 656   EVT LoIntVT = EVT::getIntegerVT(*DAG.getContext(), LoVT.getSizeInBits());
 657   EVT HiIntVT = EVT::getIntegerVT(*DAG.getContext(), HiVT.getSizeInBits());
 658   if (TLI.isBigEndian())
 659     std::swap(LoIntVT, HiIntVT);
 660
 661   SplitInteger(BitConvertToInteger(InOp), LoIntVT, HiIntVT, Lo, Hi);
 662
 663   if (TLI.isBigEndian())
 664     std::swap(Lo, Hi);
 665   Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 666   Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 667 }
 668
 669 void DAGTypeLegalizer::SplitVecRes_BUILD_VECTOR(SDNode *N, SDValue &Lo,
 670                                                 SDValue &Hi) {
 671   EVT LoVT, HiVT;
 672   SDLoc dl(N);
 673   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 674   unsigned LoNumElts = LoVT.getVectorNumElements();
 675   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+LoNumElts);
 676   Lo = DAG.getNode(ISD::BUILD_VECTOR, dl, LoVT, &LoOps[0], LoOps.size());
 677
 678   SmallVector<SDValue, 8> HiOps(N->op_begin()+LoNumElts, N->op_end());
 679   Hi = DAG.getNode(ISD::BUILD_VECTOR, dl, HiVT, &HiOps[0], HiOps.size());
 680 }
 681
 682 void DAGTypeLegalizer::SplitVecRes_CONCAT_VECTORS(SDNode *N, SDValue &Lo,
 683                                                   SDValue &Hi) {
 684   assert(!(N->getNumOperands() & 1) && "Unsupported CONCAT_VECTORS");
 685   SDLoc dl(N);
 686   unsigned NumSubvectors = N->getNumOperands() / 2;
 687   if (NumSubvectors == 1) {
 688     Lo = N->getOperand(0);
 689     Hi = N->getOperand(1);
 690     return;
 691   }
 692
 693   EVT LoVT, HiVT;
 694   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 695
 696   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+NumSubvectors);
 697   Lo = DAG.getNode(ISD::CONCAT_VECTORS, dl, LoVT, &LoOps[0], LoOps.size());
 698
 699   SmallVector<SDValue, 8> HiOps(N->op_begin()+NumSubvectors, N->op_end());
 700   Hi = DAG.getNode(ISD::CONCAT_VECTORS, dl, HiVT, &HiOps[0], HiOps.size());
 701 }
 702
 703 void DAGTypeLegalizer::SplitVecRes_EXTRACT_SUBVECTOR(SDNode *N, SDValue &Lo,
 704                                                      SDValue &Hi) {
 705   SDValue Vec = N->getOperand(0);
 706   SDValue Idx = N->getOperand(1);
 707   SDLoc dl(N);
 708
 709   EVT LoVT, HiVT;
 710   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 711
 712   Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, LoVT, Vec, Idx);
 713   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
 714   Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, HiVT, Vec,
 715                    DAG.getConstant(IdxVal + LoVT.getVectorNumElements(),
 716                                    TLI.getVectorIdxTy()));
 717 }
 718
 719 void DAGTypeLegalizer::SplitVecRes_FPOWI(SDNode *N, SDValue &Lo,
 720                                          SDValue &Hi) {
 721   SDLoc dl(N);
 722   GetSplitVector(N->getOperand(0), Lo, Hi);
 723   Lo = DAG.getNode(ISD::FPOWI, dl, Lo.getValueType(), Lo, N->getOperand(1));
 724   Hi = DAG.getNode(ISD::FPOWI, dl, Hi.getValueType(), Hi, N->getOperand(1));
 725 }
 726
 727 void DAGTypeLegalizer::SplitVecRes_InregOp(SDNode *N, SDValue &Lo,
 728                                            SDValue &Hi) {
 729   SDValue LHSLo, LHSHi;
 730   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 731   SDLoc dl(N);
 732
 733   EVT LoVT, HiVT;
 734   GetSplitDestVTs(cast<VTSDNode>(N->getOperand(1))->getVT(), LoVT, HiVT);
 735
 736   Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo,
 737                    DAG.getValueType(LoVT));
 738   Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi,
 739                    DAG.getValueType(HiVT));
 740 }
 741
 742 void DAGTypeLegalizer::SplitVecRes_INSERT_VECTOR_ELT(SDNode *N, SDValue &Lo,
 743                                                      SDValue &Hi) {
 744   SDValue Vec = N->getOperand(0);
 745   SDValue Elt = N->getOperand(1);
 746   SDValue Idx = N->getOperand(2);
 747   SDLoc dl(N);
 748   GetSplitVector(Vec, Lo, Hi);
 749
 750   if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
 751     unsigned IdxVal = CIdx->getZExtValue();
 752     unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
 753     if (IdxVal < LoNumElts)
 754       Lo = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl,
 755                        Lo.getValueType(), Lo, Elt, Idx);
 756     else
 757       Hi = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, Hi.getValueType(), Hi, Elt,
 758                        DAG.getConstant(IdxVal - LoNumElts,
 759                                        TLI.getVectorIdxTy()));
 760     return;
 761   }
 762
 763   // Spill the vector to the stack.
 764   EVT VecVT = Vec.getValueType();
 765   EVT EltVT = VecVT.getVectorElementType();
 766   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
 767   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr,
 768                                MachinePointerInfo(), false, false, 0);
 769
 770   // Store the new element.  This may be larger than the vector element type,
 771   // so use a truncating store.
 772   SDValue EltPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
 773   Type *VecType = VecVT.getTypeForEVT(*DAG.getContext());
 774   unsigned Alignment =
 775     TLI.getDataLayout()->getPrefTypeAlignment(VecType);
 776   Store = DAG.getTruncStore(Store, dl, Elt, EltPtr, MachinePointerInfo(), EltVT,
 777                             false, false, 0);
 778
 779   // Load the Lo part from the stack slot.
 780   Lo = DAG.getLoad(Lo.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
 781                    false, false, false, 0);
 782
 783   // Increment the pointer to the other part.
 784   unsigned IncrementSize = Lo.getValueType().getSizeInBits() / 8;
 785   StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 786                          DAG.getIntPtrConstant(IncrementSize));
 787
 788   // Load the Hi part from the stack slot.
 789   Hi = DAG.getLoad(Hi.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
 790                    false, false, false, MinAlign(Alignment, IncrementSize));
 791 }
 792
 793 void DAGTypeLegalizer::SplitVecRes_SCALAR_TO_VECTOR(SDNode *N, SDValue &Lo,
 794                                                     SDValue &Hi) {
 795   EVT LoVT, HiVT;
 796   SDLoc dl(N);
 797   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 798   Lo = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, LoVT, N->getOperand(0));
 799   Hi = DAG.getUNDEF(HiVT);
 800 }
 801
 802 void DAGTypeLegalizer::SplitVecRes_LOAD(LoadSDNode *LD, SDValue &Lo,
 803                                         SDValue &Hi) {
 804   assert(ISD::isUNINDEXEDLoad(LD) && "Indexed load during type legalization!");
 805   EVT LoVT, HiVT;
 806   SDLoc dl(LD);
 807   GetSplitDestVTs(LD->getValueType(0), LoVT, HiVT);
 808
 809   ISD::LoadExtType ExtType = LD->getExtensionType();
 810   SDValue Ch = LD->getChain();
 811   SDValue Ptr = LD->getBasePtr();
 812   SDValue Offset = DAG.getUNDEF(Ptr.getValueType());
 813   EVT MemoryVT = LD->getMemoryVT();
 814   unsigned Alignment = LD->getOriginalAlignment();
 815   bool isVolatile = LD->isVolatile();
 816   bool isNonTemporal = LD->isNonTemporal();
 817   bool isInvariant = LD->isInvariant();
 818
 819   EVT LoMemVT, HiMemVT;
 820   GetSplitDestVTs(MemoryVT, LoMemVT, HiMemVT);
 821
 822   Lo = DAG.getLoad(ISD::UNINDEXED, ExtType, LoVT, dl, Ch, Ptr, Offset,
 823                    LD->getPointerInfo(), LoMemVT, isVolatile, isNonTemporal,
 824                    isInvariant, Alignment);
 825
 826   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
 827   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 828                     DAG.getIntPtrConstant(IncrementSize));
 829   Hi = DAG.getLoad(ISD::UNINDEXED, ExtType, HiVT, dl, Ch, Ptr, Offset,
 830                    LD->getPointerInfo().getWithOffset(IncrementSize),
 831                    HiMemVT, isVolatile, isNonTemporal, isInvariant, Alignment);
 832
 833   // Build a factor node to remember that this load is independent of the
 834   // other one.
 835   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
 836                    Hi.getValue(1));
 837
 838   // Legalized the chain result - switch anything that used the old chain to
 839   // use the new one.
 840   ReplaceValueWith(SDValue(LD, 1), Ch);
 841 }
 842
 843 void DAGTypeLegalizer::SplitVecRes_SETCC(SDNode *N, SDValue &Lo, SDValue &Hi) {
 844   assert(N->getValueType(0).isVector() &&
 845          N->getOperand(0).getValueType().isVector() &&
 846          "Operand types must be vectors");
 847
 848   EVT LoVT, HiVT;
 849   SDLoc DL(N);
 850   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 851
 852   // Split the input.
 853   EVT InVT = N->getOperand(0).getValueType();
 854   SDValue LL, LH, RL, RH;
 855   EVT InNVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(),
 856                                LoVT.getVectorNumElements());
 857   LL = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(0),
 858                    DAG.getConstant(0, TLI.getVectorIdxTy()));
 859   LH = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(0),
 860                    DAG.getConstant(InNVT.getVectorNumElements(),
 861                    TLI.getVectorIdxTy()));
 862
 863   RL = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(1),
 864                    DAG.getConstant(0, TLI.getVectorIdxTy()));
 865   RH = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(1),
 866                    DAG.getConstant(InNVT.getVectorNumElements(),
 867                    TLI.getVectorIdxTy()));
 868
 869   Lo = DAG.getNode(N->getOpcode(), DL, LoVT, LL, RL, N->getOperand(2));
 870   Hi = DAG.getNode(N->getOpcode(), DL, HiVT, LH, RH, N->getOperand(2));
 871 }
 872
 873 void DAGTypeLegalizer::SplitVecRes_UnaryOp(SDNode *N, SDValue &Lo,
 874                                            SDValue &Hi) {
 875   // Get the dest types - they may not match the input types, e.g. int_to_fp.
 876   EVT LoVT, HiVT;
 877   SDLoc dl(N);
 878   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 879
 880   // If the input also splits, handle it directly for a compile time speedup.
 881   // Otherwise split it by hand.
 882   EVT InVT = N->getOperand(0).getValueType();
 883   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector) {
 884     GetSplitVector(N->getOperand(0), Lo, Hi);
 885   } else {
 886     EVT InNVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(),
 887                                  LoVT.getVectorNumElements());
 888     Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, InNVT, N->getOperand(0),
 889                      DAG.getConstant(0, TLI.getVectorIdxTy()));
 890     Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, InNVT, N->getOperand(0),
 891                      DAG.getConstant(InNVT.getVectorNumElements(),
 892                                      TLI.getVectorIdxTy()));
 893   }
 894
 895   if (N->getOpcode() == ISD::FP_ROUND) {
 896     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo, N->getOperand(1));
 897     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi, N->getOperand(1));
 898   } else if (N->getOpcode() == ISD::CONVERT_RNDSAT) {
 899     SDValue DTyOpLo = DAG.getValueType(LoVT);
 900     SDValue DTyOpHi = DAG.getValueType(HiVT);
 901     SDValue STyOpLo = DAG.getValueType(Lo.getValueType());
 902     SDValue STyOpHi = DAG.getValueType(Hi.getValueType());
 903     SDValue RndOp = N->getOperand(3);
 904     SDValue SatOp = N->getOperand(4);
 905     ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
 906     Lo = DAG.getConvertRndSat(LoVT, dl, Lo, DTyOpLo, STyOpLo, RndOp, SatOp,
 907                               CvtCode);
 908     Hi = DAG.getConvertRndSat(HiVT, dl, Hi, DTyOpHi, STyOpHi, RndOp, SatOp,
 909                               CvtCode);
 910   } else {
 911     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
 912     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
 913   }
 914 }
 915
 916 void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N,
 917                                                   SDValue &Lo, SDValue &Hi) {
 918   // The low and high parts of the original input give four input vectors.
 919   SDValue Inputs[4];
 920   SDLoc dl(N);
 921   GetSplitVector(N->getOperand(0), Inputs[0], Inputs[1]);
 922   GetSplitVector(N->getOperand(1), Inputs[2], Inputs[3]);
 923   EVT NewVT = Inputs[0].getValueType();
 924   unsigned NewElts = NewVT.getVectorNumElements();
 925
 926   // If Lo or Hi uses elements from at most two of the four input vectors, then
 927   // express it as a vector shuffle of those two inputs.  Otherwise extract the
 928   // input elements by hand and construct the Lo/Hi output using a BUILD_VECTOR.
 929   SmallVector<int, 16> Ops;
 930   for (unsigned High = 0; High < 2; ++High) {
 931     SDValue &Output = High ? Hi : Lo;
 932
 933     // Build a shuffle mask for the output, discovering on the fly which
 934     // input vectors to use as shuffle operands (recorded in InputUsed).
 935     // If building a suitable shuffle vector proves too hard, then bail
 936     // out with useBuildVector set.
 937     unsigned InputUsed[2] = { -1U, -1U }; // Not yet discovered.
 938     unsigned FirstMaskIdx = High * NewElts;
 939     bool useBuildVector = false;
 940     for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
 941       // The mask element.  This indexes into the input.
 942       int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
 943
 944       // The input vector this mask element indexes into.
 945       unsigned Input = (unsigned)Idx / NewElts;
 946
 947       if (Input >= array_lengthof(Inputs)) {
 948         // The mask element does not index into any input vector.
 949         Ops.push_back(-1);
 950         continue;
 951       }
 952
 953       // Turn the index into an offset from the start of the input vector.
 954       Idx -= Input * NewElts;
 955
 956       // Find or create a shuffle vector operand to hold this input.
 957       unsigned OpNo;
 958       for (OpNo = 0; OpNo < array_lengthof(InputUsed); ++OpNo) {
 959         if (InputUsed[OpNo] == Input) {
 960           // This input vector is already an operand.
 961           break;
 962         } else if (InputUsed[OpNo] == -1U) {
 963           // Create a new operand for this input vector.
 964           InputUsed[OpNo] = Input;
 965           break;
 966         }
 967       }
 968
 969       if (OpNo >= array_lengthof(InputUsed)) {
 970         // More than two input vectors used!  Give up on trying to create a
 971         // shuffle vector.  Insert all elements into a BUILD_VECTOR instead.
 972         useBuildVector = true;
 973         break;
 974       }
 975
 976       // Add the mask index for the new shuffle vector.
 977       Ops.push_back(Idx + OpNo * NewElts);
 978     }
 979
 980     if (useBuildVector) {
 981       EVT EltVT = NewVT.getVectorElementType();
 982       SmallVector<SDValue, 16> SVOps;
 983
 984       // Extract the input elements by hand.
 985       for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
 986         // The mask element.  This indexes into the input.
 987         int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
 988
 989         // The input vector this mask element indexes into.
 990         unsigned Input = (unsigned)Idx / NewElts;
 991
 992         if (Input >= array_lengthof(Inputs)) {
 993           // The mask element is "undef" or indexes off the end of the input.
 994           SVOps.push_back(DAG.getUNDEF(EltVT));
 995           continue;
 996         }
 997
 998         // Turn the index into an offset from the start of the input vector.
 999         Idx -= Input * NewElts;
1000
1001         // Extract the vector element by hand.
1002         SVOps.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT,
1003                                     Inputs[Input], DAG.getConstant(Idx,
1004                                                    TLI.getVectorIdxTy())));
1005       }
1006
1007       // Construct the Lo/Hi output using a BUILD_VECTOR.
1008       Output = DAG.getNode(ISD::BUILD_VECTOR,dl,NewVT, &SVOps[0], SVOps.size());
1009     } else if (InputUsed[0] == -1U) {
1010       // No input vectors were used!  The result is undefined.
1011       Output = DAG.getUNDEF(NewVT);
1012     } else {
1013       SDValue Op0 = Inputs[InputUsed[0]];
1014       // If only one input was used, use an undefined vector for the other.
1015       SDValue Op1 = InputUsed[1] == -1U ?
1016         DAG.getUNDEF(NewVT) : Inputs[InputUsed[1]];
1017       // At least one input vector was used.  Create a new shuffle vector.
1018       Output =  DAG.getVectorShuffle(NewVT, dl, Op0, Op1, &Ops[0]);
1019     }
1020
1021     Ops.clear();
1022   }
1023 }
1024
1025
1026 //===----------------------------------------------------------------------===//
1027 //  Operand Vector Splitting
1028 //===----------------------------------------------------------------------===//
1029
1030 /// SplitVectorOperand - This method is called when the specified operand of the
1031 /// specified node is found to need vector splitting.  At this point, all of the
1032 /// result types of the node are known to be legal, but other operands of the
1033 /// node may need legalization as well as the specified one.
1034 bool DAGTypeLegalizer::SplitVectorOperand(SDNode *N, unsigned OpNo) {
1035   DEBUG(dbgs() << "Split node operand: ";
1036         N->dump(&DAG);
1037         dbgs() << "\n");
1038   SDValue Res = SDValue();
1039
1040   // See if the target wants to custom split this node.
1041   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
1042     return false;
1043
1044   if (Res.getNode() == 0) {
1045     switch (N->getOpcode()) {
1046     default:
1047 #ifndef NDEBUG
1048       dbgs() << "SplitVectorOperand Op #" << OpNo << ": ";
1049       N->dump(&DAG);
1050       dbgs() << "\n";
1051 #endif
1052       report_fatal_error("Do not know how to split this operator's "
1053                          "operand!\n");
1054
1055     case ISD::SETCC:             Res = SplitVecOp_VSETCC(N); break;
1056     case ISD::BITCAST:           Res = SplitVecOp_BITCAST(N); break;
1057     case ISD::EXTRACT_SUBVECTOR: Res = SplitVecOp_EXTRACT_SUBVECTOR(N); break;
1058     case ISD::EXTRACT_VECTOR_ELT:Res = SplitVecOp_EXTRACT_VECTOR_ELT(N); break;
1059     case ISD::CONCAT_VECTORS:    Res = SplitVecOp_CONCAT_VECTORS(N); break;
1060     case ISD::TRUNCATE:          Res = SplitVecOp_TRUNCATE(N); break;
1061     case ISD::FP_ROUND:          Res = SplitVecOp_FP_ROUND(N); break;
1062     case ISD::STORE:
1063       Res = SplitVecOp_STORE(cast<StoreSDNode>(N), OpNo);
1064       break;
1065     case ISD::VSELECT:
1066       Res = SplitVecOp_VSELECT(N, OpNo);
1067       break;
1068     case ISD::CTTZ:
1069     case ISD::CTLZ:
1070     case ISD::CTPOP:
1071     case ISD::FP_EXTEND:
1072     case ISD::FP_TO_SINT:
1073     case ISD::FP_TO_UINT:
1074     case ISD::SINT_TO_FP:
1075     case ISD::UINT_TO_FP:
1076     case ISD::FTRUNC:
1077     case ISD::SIGN_EXTEND:
1078     case ISD::ZERO_EXTEND:
1079     case ISD::ANY_EXTEND:
1080       Res = SplitVecOp_UnaryOp(N);
1081       break;
1082     }
1083   }
1084
1085   // If the result is null, the sub-method took care of registering results etc.
1086   if (!Res.getNode()) return false;
1087
1088   // If the result is N, the sub-method updated N in place.  Tell the legalizer
1089   // core about this.
1090   if (Res.getNode() == N)
1091     return true;
1092
1093   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1094          "Invalid operand expansion");
1095
1096   ReplaceValueWith(SDValue(N, 0), Res);
1097   return false;
1098 }
1099
1100 SDValue DAGTypeLegalizer::SplitVecOp_VSELECT(SDNode *N, unsigned OpNo) {
1101   // The only possibility for an illegal operand is the mask, since result type
1102   // legalization would have handled this node already otherwise.
1103   assert(OpNo == 0 && "Illegal operand must be mask");
1104
1105   SDValue Mask = N->getOperand(0);
1106   SDValue Src0 = N->getOperand(1);
1107   SDValue Src1 = N->getOperand(2);
1108   SDLoc DL(N);
1109   EVT MaskVT = Mask.getValueType();
1110   assert(MaskVT.isVector() && "VSELECT without a vector mask?");
1111
1112   SDValue Lo, Hi;
1113   GetSplitVector(N->getOperand(0), Lo, Hi);
1114   assert(Lo.getValueType() == Hi.getValueType() &&
1115          "Lo and Hi have differing types");
1116
1117   unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
1118   unsigned HiNumElts = Hi.getValueType().getVectorNumElements();
1119   assert(LoNumElts == HiNumElts && "Asymmetric vector split?");
1120
1121   LLVMContext &Ctx = *DAG.getContext();
1122   SDValue Zero = DAG.getConstant(0, TLI.getVectorIdxTy());
1123   SDValue LoElts = DAG.getConstant(LoNumElts, TLI.getVectorIdxTy());
1124   EVT Src0VT = Src0.getValueType();
1125   EVT Src0EltTy = Src0VT.getVectorElementType();
1126   EVT MaskEltTy = MaskVT.getVectorElementType();
1127
1128   EVT LoOpVT = EVT::getVectorVT(Ctx, Src0EltTy, LoNumElts);
1129   EVT LoMaskVT = EVT::getVectorVT(Ctx, MaskEltTy, LoNumElts);
1130   EVT HiOpVT = EVT::getVectorVT(Ctx, Src0EltTy, HiNumElts);
1131   EVT HiMaskVT = EVT::getVectorVT(Ctx, MaskEltTy, HiNumElts);
1132
1133   SDValue LoOp0 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, LoOpVT, Src0, Zero);
1134   SDValue LoOp1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, LoOpVT, Src1, Zero);
1135
1136   SDValue HiOp0 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, HiOpVT, Src0, LoElts);
1137   SDValue HiOp1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, HiOpVT, Src1, LoElts);
1138
1139   SDValue LoMask =
1140     DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, LoMaskVT, Mask, Zero);
1141   SDValue HiMask =
1142     DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, HiMaskVT, Mask, LoElts);
1143
1144   SDValue LoSelect =
1145     DAG.getNode(ISD::VSELECT, DL, LoOpVT, LoMask, LoOp0, LoOp1);
1146   SDValue HiSelect =
1147     DAG.getNode(ISD::VSELECT, DL, HiOpVT, HiMask, HiOp0, HiOp1);
1148
1149   return DAG.getNode(ISD::CONCAT_VECTORS, DL, Src0VT, LoSelect, HiSelect);
1150 }
1151
1152 SDValue DAGTypeLegalizer::SplitVecOp_UnaryOp(SDNode *N) {
1153   // The result has a legal vector type, but the input needs splitting.
1154   EVT ResVT = N->getValueType(0);
1155   SDValue Lo, Hi;
1156   SDLoc dl(N);
1157   GetSplitVector(N->getOperand(0), Lo, Hi);
1158   EVT InVT = Lo.getValueType();
1159
1160   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
1161                                InVT.getVectorNumElements());
1162
1163   Lo = DAG.getNode(N->getOpcode(), dl, OutVT, Lo);
1164   Hi = DAG.getNode(N->getOpcode(), dl, OutVT, Hi);
1165
1166   return DAG.getNode(ISD::CONCAT_VECTORS, dl, ResVT, Lo, Hi);
1167 }
1168
1169 SDValue DAGTypeLegalizer::SplitVecOp_BITCAST(SDNode *N) {
1170   // For example, i64 = BITCAST v4i16 on alpha.  Typically the vector will
1171   // end up being split all the way down to individual components.  Convert the
1172   // split pieces into integers and reassemble.
1173   SDValue Lo, Hi;
1174   GetSplitVector(N->getOperand(0), Lo, Hi);
1175   Lo = BitConvertToInteger(Lo);
1176   Hi = BitConvertToInteger(Hi);
1177
1178   if (TLI.isBigEndian())
1179     std::swap(Lo, Hi);
1180
1181   return DAG.getNode(ISD::BITCAST, SDLoc(N), N->getValueType(0),
1182                      JoinIntegers(Lo, Hi));
1183 }
1184
1185 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
1186   // We know that the extracted result type is legal.
1187   EVT SubVT = N->getValueType(0);
1188   SDValue Idx = N->getOperand(1);
1189   SDLoc dl(N);
1190   SDValue Lo, Hi;
1191   GetSplitVector(N->getOperand(0), Lo, Hi);
1192
1193   uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1194   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1195
1196   if (IdxVal < LoElts) {
1197     assert(IdxVal + SubVT.getVectorNumElements() <= LoElts &&
1198            "Extracted subvector crosses vector split!");
1199     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Lo, Idx);
1200   } else {
1201     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Hi,
1202                        DAG.getConstant(IdxVal - LoElts, Idx.getValueType()));
1203   }
1204 }
1205
1206 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
1207   SDValue Vec = N->getOperand(0);
1208   SDValue Idx = N->getOperand(1);
1209   EVT VecVT = Vec.getValueType();
1210
1211   if (isa<ConstantSDNode>(Idx)) {
1212     uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1213     assert(IdxVal < VecVT.getVectorNumElements() && "Invalid vector index!");
1214
1215     SDValue Lo, Hi;
1216     GetSplitVector(Vec, Lo, Hi);
1217
1218     uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1219
1220     if (IdxVal < LoElts)
1221       return SDValue(DAG.UpdateNodeOperands(N, Lo, Idx), 0);
1222     return SDValue(DAG.UpdateNodeOperands(N, Hi,
1223                                   DAG.getConstant(IdxVal - LoElts,
1224                                                   Idx.getValueType())), 0);
1225   }
1226
1227   // Store the vector to the stack.
1228   EVT EltVT = VecVT.getVectorElementType();
1229   SDLoc dl(N);
1230   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
1231   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr,
1232                                MachinePointerInfo(), false, false, 0);
1233
1234   // Load back the required element.
1235   StackPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
1236   return DAG.getExtLoad(ISD::EXTLOAD, dl, N->getValueType(0), Store, StackPtr,
1237                         MachinePointerInfo(), EltVT, false, false, 0);
1238 }
1239
1240 SDValue DAGTypeLegalizer::SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo) {
1241   assert(N->isUnindexed() && "Indexed store of vector?");
1242   assert(OpNo == 1 && "Can only split the stored value");
1243   SDLoc DL(N);
1244
1245   bool isTruncating = N->isTruncatingStore();
1246   SDValue Ch  = N->getChain();
1247   SDValue Ptr = N->getBasePtr();
1248   EVT MemoryVT = N->getMemoryVT();
1249   unsigned Alignment = N->getOriginalAlignment();
1250   bool isVol = N->isVolatile();
1251   bool isNT = N->isNonTemporal();
1252   SDValue Lo, Hi;
1253   GetSplitVector(N->getOperand(1), Lo, Hi);
1254
1255   EVT LoMemVT, HiMemVT;
1256   GetSplitDestVTs(MemoryVT, LoMemVT, HiMemVT);
1257
1258   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
1259
1260   if (isTruncating)
1261     Lo = DAG.getTruncStore(Ch, DL, Lo, Ptr, N->getPointerInfo(),
1262                            LoMemVT, isVol, isNT, Alignment);
1263   else
1264     Lo = DAG.getStore(Ch, DL, Lo, Ptr, N->getPointerInfo(),
1265                       isVol, isNT, Alignment);
1266
1267   // Increment the pointer to the other half.
1268   Ptr = DAG.getNode(ISD::ADD, DL, Ptr.getValueType(), Ptr,
1269                     DAG.getIntPtrConstant(IncrementSize));
1270
1271   if (isTruncating)
1272     Hi = DAG.getTruncStore(Ch, DL, Hi, Ptr,
1273                            N->getPointerInfo().getWithOffset(IncrementSize),
1274                            HiMemVT, isVol, isNT, Alignment);
1275   else
1276     Hi = DAG.getStore(Ch, DL, Hi, Ptr,
1277                       N->getPointerInfo().getWithOffset(IncrementSize),
1278                       isVol, isNT, Alignment);
1279
1280   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
1281 }
1282
1283 SDValue DAGTypeLegalizer::SplitVecOp_CONCAT_VECTORS(SDNode *N) {
1284   SDLoc DL(N);
1285
1286   // The input operands all must have the same type, and we know the result
1287   // type is valid.  Convert this to a buildvector which extracts all the
1288   // input elements.
1289   // TODO: If the input elements are power-two vectors, we could convert this to
1290   // a new CONCAT_VECTORS node with elements that are half-wide.
1291   SmallVector<SDValue, 32> Elts;
1292   EVT EltVT = N->getValueType(0).getVectorElementType();
1293   for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
1294     SDValue Op = N->getOperand(op);
1295     for (unsigned i = 0, e = Op.getValueType().getVectorNumElements();
1296          i != e; ++i) {
1297       Elts.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, EltVT,
1298                                  Op, DAG.getConstant(i, TLI.getVectorIdxTy())));
1299
1300     }
1301   }
1302
1303   return DAG.getNode(ISD::BUILD_VECTOR, DL, N->getValueType(0),
1304                      &Elts[0], Elts.size());
1305 }
1306
1307 SDValue DAGTypeLegalizer::SplitVecOp_TRUNCATE(SDNode *N) {
1308   // The result type is legal, but the input type is illegal.  If splitting
1309   // ends up with the result type of each half still being legal, just
1310   // do that.  If, however, that would result in an illegal result type,
1311   // we can try to get more clever with power-two vectors. Specifically,
1312   // split the input type, but also widen the result element size, then
1313   // concatenate the halves and truncate again.  For example, consider a target
1314   // where v8i8 is legal and v8i32 is not (ARM, which doesn't have 256-bit
1315   // vectors). To perform a "%res = v8i8 trunc v8i32 %in" we do:
1316   //   %inlo = v4i32 extract_subvector %in, 0
1317   //   %inhi = v4i32 extract_subvector %in, 4
1318   //   %lo16 = v4i16 trunc v4i32 %inlo
1319   //   %hi16 = v4i16 trunc v4i32 %inhi
1320   //   %in16 = v8i16 concat_vectors v4i16 %lo16, v4i16 %hi16
1321   //   %res = v8i8 trunc v8i16 %in16
1322   //
1323   // Without this transform, the original truncate would end up being
1324   // scalarized, which is pretty much always a last resort.
1325   SDValue InVec = N->getOperand(0);
1326   EVT InVT = InVec->getValueType(0);
1327   EVT OutVT = N->getValueType(0);
1328   unsigned NumElements = OutVT.getVectorNumElements();
1329   // Widening should have already made sure this is a power-two vector
1330   // if we're trying to split it at all. assert() that's true, just in case.
1331   assert(!(NumElements & 1) && "Splitting vector, but not in half!");
1332
1333   unsigned InElementSize = InVT.getVectorElementType().getSizeInBits();
1334   unsigned OutElementSize = OutVT.getVectorElementType().getSizeInBits();
1335
1336   // If the input elements are only 1/2 the width of the result elements,
1337   // just use the normal splitting. Our trick only work if there's room
1338   // to split more than once.
1339   if (InElementSize <= OutElementSize * 2)
1340     return SplitVecOp_UnaryOp(N);
1341   SDLoc DL(N);
1342
1343   // Extract the halves of the input via extract_subvector.
1344   EVT SplitVT = EVT::getVectorVT(*DAG.getContext(),
1345                                  InVT.getVectorElementType(), NumElements/2);
1346   SDValue InLoVec = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, InVec,
1347                                 DAG.getConstant(0, TLI.getVectorIdxTy()));
1348   SDValue InHiVec = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, InVec,
1349                                 DAG.getConstant(NumElements/2,
1350                                 TLI.getVectorIdxTy()));
1351   // Truncate them to 1/2 the element size.
1352   EVT HalfElementVT = EVT::getIntegerVT(*DAG.getContext(), InElementSize/2);
1353   EVT HalfVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT,
1354                                 NumElements/2);
1355   SDValue HalfLo = DAG.getNode(ISD::TRUNCATE, DL, HalfVT, InLoVec);
1356   SDValue HalfHi = DAG.getNode(ISD::TRUNCATE, DL, HalfVT, InHiVec);
1357   // Concatenate them to get the full intermediate truncation result.
1358   EVT InterVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT, NumElements);
1359   SDValue InterVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InterVT, HalfLo,
1360                                  HalfHi);
1361   // Now finish up by truncating all the way down to the original result
1362   // type. This should normally be something that ends up being legal directly,
1363   // but in theory if a target has very wide vectors and an annoyingly
1364   // restricted set of legal types, this split can chain to build things up.
1365   return DAG.getNode(ISD::TRUNCATE, DL, OutVT, InterVec);
1366 }
1367
1368 SDValue DAGTypeLegalizer::SplitVecOp_VSETCC(SDNode *N) {
1369   assert(N->getValueType(0).isVector() &&
1370          N->getOperand(0).getValueType().isVector() &&
1371          "Operand types must be vectors");
1372   // The result has a legal vector type, but the input needs splitting.
1373   SDValue Lo0, Hi0, Lo1, Hi1, LoRes, HiRes;
1374   SDLoc DL(N);
1375   GetSplitVector(N->getOperand(0), Lo0, Hi0);
1376   GetSplitVector(N->getOperand(1), Lo1, Hi1);
1377   unsigned PartElements = Lo0.getValueType().getVectorNumElements();
1378   EVT PartResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, PartElements);
1379   EVT WideResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, 2*PartElements);
1380
1381   LoRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Lo0, Lo1, N->getOperand(2));
1382   HiRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Hi0, Hi1, N->getOperand(2));
1383   SDValue Con = DAG.getNode(ISD::CONCAT_VECTORS, DL, WideResVT, LoRes, HiRes);
1384   return PromoteTargetBoolean(Con, N->getValueType(0));
1385 }
1386
1387
1388 SDValue DAGTypeLegalizer::SplitVecOp_FP_ROUND(SDNode *N) {
1389   // The result has a legal vector type, but the input needs splitting.
1390   EVT ResVT = N->getValueType(0);
1391   SDValue Lo, Hi;
1392   SDLoc DL(N);
1393   GetSplitVector(N->getOperand(0), Lo, Hi);
1394   EVT InVT = Lo.getValueType();
1395
1396   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
1397                                InVT.getVectorNumElements());
1398
1399   Lo = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Lo, N->getOperand(1));
1400   Hi = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Hi, N->getOperand(1));
1401
1402   return DAG.getNode(ISD::CONCAT_VECTORS, DL, ResVT, Lo, Hi);
1403 }
1404
1405
1406
1407 //===----------------------------------------------------------------------===//
1408 //  Result Vector Widening
1409 //===----------------------------------------------------------------------===//
1410
1411 void DAGTypeLegalizer::WidenVectorResult(SDNode *N, unsigned ResNo) {
1412   DEBUG(dbgs() << "Widen node result " << ResNo << ": ";
1413         N->dump(&DAG);
1414         dbgs() << "\n");
1415
1416   // See if the target wants to custom widen this node.
1417   if (CustomWidenLowerNode(N, N->getValueType(ResNo)))
1418     return;
1419
1420   SDValue Res = SDValue();
1421   switch (N->getOpcode()) {
1422   default:
1423 #ifndef NDEBUG
1424     dbgs() << "WidenVectorResult #" << ResNo << ": ";
1425     N->dump(&DAG);
1426     dbgs() << "\n";
1427 #endif
1428     llvm_unreachable("Do not know how to widen the result of this operator!");
1429
1430   case ISD::MERGE_VALUES:      Res = WidenVecRes_MERGE_VALUES(N, ResNo); break;
1431   case ISD::BITCAST:           Res = WidenVecRes_BITCAST(N); break;
1432   case ISD::BUILD_VECTOR:      Res = WidenVecRes_BUILD_VECTOR(N); break;
1433   case ISD::CONCAT_VECTORS:    Res = WidenVecRes_CONCAT_VECTORS(N); break;
1434   case ISD::CONVERT_RNDSAT:    Res = WidenVecRes_CONVERT_RNDSAT(N); break;
1435   case ISD::EXTRACT_SUBVECTOR: Res = WidenVecRes_EXTRACT_SUBVECTOR(N); break;
1436   case ISD::FP_ROUND_INREG:    Res = WidenVecRes_InregOp(N); break;
1437   case ISD::INSERT_VECTOR_ELT: Res = WidenVecRes_INSERT_VECTOR_ELT(N); break;
1438   case ISD::LOAD:              Res = WidenVecRes_LOAD(N); break;
1439   case ISD::SCALAR_TO_VECTOR:  Res = WidenVecRes_SCALAR_TO_VECTOR(N); break;
1440   case ISD::SIGN_EXTEND_INREG: Res = WidenVecRes_InregOp(N); break;
1441   case ISD::VSELECT:
1442   case ISD::SELECT:            Res = WidenVecRes_SELECT(N); break;
1443   case ISD::SELECT_CC:         Res = WidenVecRes_SELECT_CC(N); break;
1444   case ISD::SETCC:             Res = WidenVecRes_SETCC(N); break;
1445   case ISD::UNDEF:             Res = WidenVecRes_UNDEF(N); break;
1446   case ISD::VECTOR_SHUFFLE:
1447     Res = WidenVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N));
1448     break;
1449   case ISD::ADD:
1450   case ISD::AND:
1451   case ISD::BSWAP:
1452   case ISD::FADD:
1453   case ISD::FCOPYSIGN:
1454   case ISD::FDIV:
1455   case ISD::FMUL:
1456   case ISD::FPOW:
1457   case ISD::FREM:
1458   case ISD::FSUB:
1459   case ISD::MUL:
1460   case ISD::MULHS:
1461   case ISD::MULHU:
1462   case ISD::OR:
1463   case ISD::SDIV:
1464   case ISD::SREM:
1465   case ISD::UDIV:
1466   case ISD::UREM:
1467   case ISD::SUB:
1468   case ISD::XOR:
1469     Res = WidenVecRes_Binary(N);
1470     break;
1471
1472   case ISD::FPOWI:
1473     Res = WidenVecRes_POWI(N);
1474     break;
1475
1476   case ISD::SHL:
1477   case ISD::SRA:
1478   case ISD::SRL:
1479     Res = WidenVecRes_Shift(N);
1480     break;
1481
1482   case ISD::ANY_EXTEND:
1483   case ISD::FP_EXTEND:
1484   case ISD::FP_ROUND:
1485   case ISD::FP_TO_SINT:
1486   case ISD::FP_TO_UINT:
1487   case ISD::SIGN_EXTEND:
1488   case ISD::SINT_TO_FP:
1489   case ISD::TRUNCATE:
1490   case ISD::UINT_TO_FP:
1491   case ISD::ZERO_EXTEND:
1492     Res = WidenVecRes_Convert(N);
1493     break;
1494
1495   case ISD::CTLZ:
1496   case ISD::CTPOP:
1497   case ISD::CTTZ:
1498   case ISD::FABS:
1499   case ISD::FCEIL:
1500   case ISD::FCOS:
1501   case ISD::FEXP:
1502   case ISD::FEXP2:
1503   case ISD::FFLOOR:
1504   case ISD::FLOG:
1505   case ISD::FLOG10:
1506   case ISD::FLOG2:
1507   case ISD::FNEARBYINT:
1508   case ISD::FNEG:
1509   case ISD::FRINT:
1510   case ISD::FSIN:
1511   case ISD::FSQRT:
1512   case ISD::FTRUNC:
1513     Res = WidenVecRes_Unary(N);
1514     break;
1515   case ISD::FMA:
1516     Res = WidenVecRes_Ternary(N);
1517     break;
1518   }
1519
1520   // If Res is null, the sub-method took care of registering the result.
1521   if (Res.getNode())
1522     SetWidenedVector(SDValue(N, ResNo), Res);
1523 }
1524
1525 SDValue DAGTypeLegalizer::WidenVecRes_Ternary(SDNode *N) {
1526   // Ternary op widening.
1527   SDLoc dl(N);
1528   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1529   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1530   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1531   SDValue InOp3 = GetWidenedVector(N->getOperand(2));
1532   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, InOp3);
1533 }
1534
1535 SDValue DAGTypeLegalizer::WidenVecRes_Binary(SDNode *N) {
1536   // Binary op widening.
1537   unsigned Opcode = N->getOpcode();
1538   SDLoc dl(N);
1539   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1540   EVT WidenEltVT = WidenVT.getVectorElementType();
1541   EVT VT = WidenVT;
1542   unsigned NumElts =  VT.getVectorNumElements();
1543   while (!TLI.isTypeLegal(VT) && NumElts != 1) {
1544     NumElts = NumElts / 2;
1545     VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
1546   }
1547
1548   if (NumElts != 1 && !TLI.canOpTrap(N->getOpcode(), VT)) {
1549     // Operation doesn't trap so just widen as normal.
1550     SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1551     SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1552     return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2);
1553   }
1554
1555   // No legal vector version so unroll the vector operation and then widen.
1556   if (NumElts == 1)
1557     return DAG.UnrollVectorOp(N, WidenVT.getVectorNumElements());
1558
1559   // Since the operation can trap, apply operation on the original vector.
1560   EVT MaxVT = VT;
1561   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1562   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1563   unsigned CurNumElts = N->getValueType(0).getVectorNumElements();
1564
1565   SmallVector<SDValue, 16> ConcatOps(CurNumElts);
1566   unsigned ConcatEnd = 0;  // Current ConcatOps index.
1567   int Idx = 0;        // Current Idx into input vectors.
1568
1569   // NumElts := greatest legal vector size (at most WidenVT)
1570   // while (orig. vector has unhandled elements) {
1571   //   take munches of size NumElts from the beginning and add to ConcatOps
1572   //   NumElts := next smaller supported vector size or 1
1573   // }
1574   while (CurNumElts != 0) {
1575     while (CurNumElts >= NumElts) {
1576       SDValue EOp1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, InOp1,
1577                                  DAG.getConstant(Idx, TLI.getVectorIdxTy()));
1578       SDValue EOp2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, InOp2,
1579                                  DAG.getConstant(Idx, TLI.getVectorIdxTy()));
1580       ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, VT, EOp1, EOp2);
1581       Idx += NumElts;
1582       CurNumElts -= NumElts;
1583     }
1584     do {
1585       NumElts = NumElts / 2;
1586       VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
1587     } while (!TLI.isTypeLegal(VT) && NumElts != 1);
1588
1589     if (NumElts == 1) {
1590       for (unsigned i = 0; i != CurNumElts; ++i, ++Idx) {
1591         SDValue EOp1 = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT,
1592                                    InOp1, DAG.getConstant(Idx,
1593                                                          TLI.getVectorIdxTy()));
1594         SDValue EOp2 = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT,
1595                                    InOp2, DAG.getConstant(Idx,
1596                                                          TLI.getVectorIdxTy()));
1597         ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, WidenEltVT,
1598                                              EOp1, EOp2);
1599       }
1600       CurNumElts = 0;
1601     }
1602   }
1603
1604   // Check to see if we have a single operation with the widen type.
1605   if (ConcatEnd == 1) {
1606     VT = ConcatOps[0].getValueType();
1607     if (VT == WidenVT)
1608       return ConcatOps[0];
1609   }
1610
1611   // while (Some element of ConcatOps is not of type MaxVT) {
1612   //   From the end of ConcatOps, collect elements of the same type and put
1613   //   them into an op of the next larger supported type
1614   // }
1615   while (ConcatOps[ConcatEnd-1].getValueType() != MaxVT) {
1616     Idx = ConcatEnd - 1;
1617     VT = ConcatOps[Idx--].getValueType();
1618     while (Idx >= 0 && ConcatOps[Idx].getValueType() == VT)
1619       Idx--;
1620
1621     int NextSize = VT.isVector() ? VT.getVectorNumElements() : 1;
1622     EVT NextVT;
1623     do {
1624       NextSize *= 2;
1625       NextVT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NextSize);
1626     } while (!TLI.isTypeLegal(NextVT));
1627
1628     if (!VT.isVector()) {
1629       // Scalar type, create an INSERT_VECTOR_ELEMENT of type NextVT
1630       SDValue VecOp = DAG.getUNDEF(NextVT);
1631       unsigned NumToInsert = ConcatEnd - Idx - 1;
1632       for (unsigned i = 0, OpIdx = Idx+1; i < NumToInsert; i++, OpIdx++) {
1633         VecOp = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NextVT, VecOp,
1634                             ConcatOps[OpIdx], DAG.getConstant(i,
1635                                                          TLI.getVectorIdxTy()));
1636       }
1637       ConcatOps[Idx+1] = VecOp;
1638       ConcatEnd = Idx + 2;
1639     } else {
1640       // Vector type, create a CONCAT_VECTORS of type NextVT
1641       SDValue undefVec = DAG.getUNDEF(VT);
1642       unsigned OpsToConcat = NextSize/VT.getVectorNumElements();
1643       SmallVector<SDValue, 16> SubConcatOps(OpsToConcat);
1644       unsigned RealVals = ConcatEnd - Idx - 1;
1645       unsigned SubConcatEnd = 0;
1646       unsigned SubConcatIdx = Idx + 1;
1647       while (SubConcatEnd < RealVals)
1648         SubConcatOps[SubConcatEnd++] = ConcatOps[++Idx];
1649       while (SubConcatEnd < OpsToConcat)
1650         SubConcatOps[SubConcatEnd++] = undefVec;
1651       ConcatOps[SubConcatIdx] = DAG.getNode(ISD::CONCAT_VECTORS, dl,
1652                                             NextVT, &SubConcatOps[0],
1653                                             OpsToConcat);
1654       ConcatEnd = SubConcatIdx + 1;
1655     }
1656   }
1657
1658   // Check to see if we have a single operation with the widen type.
1659   if (ConcatEnd == 1) {
1660     VT = ConcatOps[0].getValueType();
1661     if (VT == WidenVT)
1662       return ConcatOps[0];
1663   }
1664
1665   // add undefs of size MaxVT until ConcatOps grows to length of WidenVT
1666   unsigned NumOps = WidenVT.getVectorNumElements()/MaxVT.getVectorNumElements();
1667   if (NumOps != ConcatEnd ) {
1668     SDValue UndefVal = DAG.getUNDEF(MaxVT);
1669     for (unsigned j = ConcatEnd; j < NumOps; ++j)
1670       ConcatOps[j] = UndefVal;
1671   }
1672   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &ConcatOps[0], NumOps);
1673 }
1674
1675 SDValue DAGTypeLegalizer::WidenVecRes_Convert(SDNode *N) {
1676   SDValue InOp = N->getOperand(0);
1677   SDLoc DL(N);
1678
1679   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1680   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1681
1682   EVT InVT = InOp.getValueType();
1683   EVT InEltVT = InVT.getVectorElementType();
1684   EVT InWidenVT = EVT::getVectorVT(*DAG.getContext(), InEltVT, WidenNumElts);
1685
1686   unsigned Opcode = N->getOpcode();
1687   unsigned InVTNumElts = InVT.getVectorNumElements();
1688
1689   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
1690     InOp = GetWidenedVector(N->getOperand(0));
1691     InVT = InOp.getValueType();
1692     InVTNumElts = InVT.getVectorNumElements();
1693     if (InVTNumElts == WidenNumElts) {
1694       if (N->getNumOperands() == 1)
1695         return DAG.getNode(Opcode, DL, WidenVT, InOp);
1696       return DAG.getNode(Opcode, DL, WidenVT, InOp, N->getOperand(1));
1697     }
1698   }
1699
1700   if (TLI.isTypeLegal(InWidenVT)) {
1701     // Because the result and the input are different vector types, widening
1702     // the result could create a legal type but widening the input might make
1703     // it an illegal type that might lead to repeatedly splitting the input
1704     // and then widening it. To avoid this, we widen the input only if
1705     // it results in a legal type.
1706     if (WidenNumElts % InVTNumElts == 0) {
1707       // Widen the input and call convert on the widened input vector.
1708       unsigned NumConcat = WidenNumElts/InVTNumElts;
1709       SmallVector<SDValue, 16> Ops(NumConcat);
1710       Ops[0] = InOp;
1711       SDValue UndefVal = DAG.getUNDEF(InVT);
1712       for (unsigned i = 1; i != NumConcat; ++i)
1713         Ops[i] = UndefVal;
1714       SDValue InVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InWidenVT,
1715                                   &Ops[0], NumConcat);
1716       if (N->getNumOperands() == 1)
1717         return DAG.getNode(Opcode, DL, WidenVT, InVec);
1718       return DAG.getNode(Opcode, DL, WidenVT, InVec, N->getOperand(1));
1719     }
1720
1721     if (InVTNumElts % WidenNumElts == 0) {
1722       SDValue InVal = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InWidenVT,
1723                                   InOp, DAG.getConstant(0,
1724                                                         TLI.getVectorIdxTy()));
1725       // Extract the input and convert the shorten input vector.
1726       if (N->getNumOperands() == 1)
1727         return DAG.getNode(Opcode, DL, WidenVT, InVal);
1728       return DAG.getNode(Opcode, DL, WidenVT, InVal, N->getOperand(1));
1729     }
1730   }
1731
1732   // Otherwise unroll into some nasty scalar code and rebuild the vector.
1733   SmallVector<SDValue, 16> Ops(WidenNumElts);
1734   EVT EltVT = WidenVT.getVectorElementType();
1735   unsigned MinElts = std::min(InVTNumElts, WidenNumElts);
1736   unsigned i;
1737   for (i=0; i < MinElts; ++i) {
1738     SDValue Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, InEltVT, InOp,
1739                               DAG.getConstant(i, TLI.getVectorIdxTy()));
1740     if (N->getNumOperands() == 1)
1741       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val);
1742     else
1743       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val, N->getOperand(1));
1744   }
1745
1746   SDValue UndefVal = DAG.getUNDEF(EltVT);
1747   for (; i < WidenNumElts; ++i)
1748     Ops[i] = UndefVal;
1749
1750   return DAG.getNode(ISD::BUILD_VECTOR, DL, WidenVT, &Ops[0], WidenNumElts);
1751 }
1752
1753 SDValue DAGTypeLegalizer::WidenVecRes_POWI(SDNode *N) {
1754   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1755   SDValue InOp = GetWidenedVector(N->getOperand(0));
1756   SDValue ShOp = N->getOperand(1);
1757   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
1758 }
1759
1760 SDValue DAGTypeLegalizer::WidenVecRes_Shift(SDNode *N) {
1761   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1762   SDValue InOp = GetWidenedVector(N->getOperand(0));
1763   SDValue ShOp = N->getOperand(1);
1764
1765   EVT ShVT = ShOp.getValueType();
1766   if (getTypeAction(ShVT) == TargetLowering::TypeWidenVector) {
1767     ShOp = GetWidenedVector(ShOp);
1768     ShVT = ShOp.getValueType();
1769   }
1770   EVT ShWidenVT = EVT::getVectorVT(*DAG.getContext(),
1771                                    ShVT.getVectorElementType(),
1772                                    WidenVT.getVectorNumElements());
1773   if (ShVT != ShWidenVT)
1774     ShOp = ModifyToType(ShOp, ShWidenVT);
1775
1776   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
1777 }
1778
1779 SDValue DAGTypeLegalizer::WidenVecRes_Unary(SDNode *N) {
1780   // Unary op widening.
1781   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1782   SDValue InOp = GetWidenedVector(N->getOperand(0));
1783   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp);
1784 }
1785
1786 SDValue DAGTypeLegalizer::WidenVecRes_InregOp(SDNode *N) {
1787   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1788   EVT ExtVT = EVT::getVectorVT(*DAG.getContext(),
1789                                cast<VTSDNode>(N->getOperand(1))->getVT()
1790                                  .getVectorElementType(),
1791                                WidenVT.getVectorNumElements());
1792   SDValue WidenLHS = GetWidenedVector(N->getOperand(0));
1793   return DAG.getNode(N->getOpcode(), SDLoc(N),
1794                      WidenVT, WidenLHS, DAG.getValueType(ExtVT));
1795 }
1796
1797 SDValue DAGTypeLegalizer::WidenVecRes_MERGE_VALUES(SDNode *N, unsigned ResNo) {
1798   SDValue WidenVec = DisintegrateMERGE_VALUES(N, ResNo);
1799   return GetWidenedVector(WidenVec);
1800 }
1801
1802 SDValue DAGTypeLegalizer::WidenVecRes_BITCAST(SDNode *N) {
1803   SDValue InOp = N->getOperand(0);
1804   EVT InVT = InOp.getValueType();
1805   EVT VT = N->getValueType(0);
1806   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
1807   SDLoc dl(N);
1808
1809   switch (getTypeAction(InVT)) {
1810   case TargetLowering::TypeLegal:
1811     break;
1812   case TargetLowering::TypePromoteInteger:
1813     // If the incoming type is a vector that is being promoted, then
1814     // we know that the elements are arranged differently and that we
1815     // must perform the conversion using a stack slot.
1816     if (InVT.isVector())
1817       break;
1818
1819     // If the InOp is promoted to the same size, convert it.  Otherwise,
1820     // fall out of the switch and widen the promoted input.
1821     InOp = GetPromotedInteger(InOp);
1822     InVT = InOp.getValueType();
1823     if (WidenVT.bitsEq(InVT))
1824       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
1825     break;
1826   case TargetLowering::TypeSoftenFloat:
1827   case TargetLowering::TypeExpandInteger:
1828   case TargetLowering::TypeExpandFloat:
1829   case TargetLowering::TypeScalarizeVector:
1830   case TargetLowering::TypeSplitVector:
1831     break;
1832   case TargetLowering::TypeWidenVector:
1833     // If the InOp is widened to the same size, convert it.  Otherwise, fall
1834     // out of the switch and widen the widened input.
1835     InOp = GetWidenedVector(InOp);
1836     InVT = InOp.getValueType();
1837     if (WidenVT.bitsEq(InVT))
1838       // The input widens to the same size. Convert to the widen value.
1839       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
1840     break;
1841   }
1842
1843   unsigned WidenSize = WidenVT.getSizeInBits();
1844   unsigned InSize = InVT.getSizeInBits();
1845   // x86mmx is not an acceptable vector element type, so don't try.
1846   if (WidenSize % InSize == 0 && InVT != MVT::x86mmx) {
1847     // Determine new input vector type.  The new input vector type will use
1848     // the same element type (if its a vector) or use the input type as a
1849     // vector.  It is the same size as the type to widen to.
1850     EVT NewInVT;
1851     unsigned NewNumElts = WidenSize / InSize;
1852     if (InVT.isVector()) {
1853       EVT InEltVT = InVT.getVectorElementType();
1854       NewInVT = EVT::getVectorVT(*DAG.getContext(), InEltVT,
1855                                  WidenSize / InEltVT.getSizeInBits());
1856     } else {
1857       NewInVT = EVT::getVectorVT(*DAG.getContext(), InVT, NewNumElts);
1858     }
1859
1860     if (TLI.isTypeLegal(NewInVT)) {
1861       // Because the result and the input are different vector types, widening
1862       // the result could create a legal type but widening the input might make
1863       // it an illegal type that might lead to repeatedly splitting the input
1864       // and then widening it. To avoid this, we widen the input only if
1865       // it results in a legal type.
1866       SmallVector<SDValue, 16> Ops(NewNumElts);
1867       SDValue UndefVal = DAG.getUNDEF(InVT);
1868       Ops[0] = InOp;
1869       for (unsigned i = 1; i < NewNumElts; ++i)
1870         Ops[i] = UndefVal;
1871
1872       SDValue NewVec;
1873       if (InVT.isVector())
1874         NewVec = DAG.getNode(ISD::CONCAT_VECTORS, dl,
1875                              NewInVT, &Ops[0], NewNumElts);
1876       else
1877         NewVec = DAG.getNode(ISD::BUILD_VECTOR, dl,
1878                              NewInVT, &Ops[0], NewNumElts);
1879       return DAG.getNode(ISD::BITCAST, dl, WidenVT, NewVec);
1880     }
1881   }
1882
1883   return CreateStackStoreLoad(InOp, WidenVT);
1884 }
1885
1886 SDValue DAGTypeLegalizer::WidenVecRes_BUILD_VECTOR(SDNode *N) {
1887   SDLoc dl(N);
1888   // Build a vector with undefined for the new nodes.
1889   EVT VT = N->getValueType(0);
1890
1891   // Integer BUILD_VECTOR operands may be larger than the node's vector element
1892   // type. The UNDEFs need to have the same type as the existing operands.
1893   EVT EltVT = N->getOperand(0).getValueType();
1894   unsigned NumElts = VT.getVectorNumElements();
1895
1896   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
1897   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1898
1899   SmallVector<SDValue, 16> NewOps(N->op_begin(), N->op_end());
1900   assert(WidenNumElts >= NumElts && "Shrinking vector instead of widening!");
1901   NewOps.append(WidenNumElts - NumElts, DAG.getUNDEF(EltVT));
1902
1903   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &NewOps[0], NewOps.size());
1904 }
1905
1906 SDValue DAGTypeLegalizer::WidenVecRes_CONCAT_VECTORS(SDNode *N) {
1907   EVT InVT = N->getOperand(0).getValueType();
1908   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1909   SDLoc dl(N);
1910   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1911   unsigned NumInElts = InVT.getVectorNumElements();
1912   unsigned NumOperands = N->getNumOperands();
1913
1914   bool InputWidened = false; // Indicates we need to widen the input.
1915   if (getTypeAction(InVT) != TargetLowering::TypeWidenVector) {
1916     if (WidenVT.getVectorNumElements() % InVT.getVectorNumElements() == 0) {
1917       // Add undef vectors to widen to correct length.
1918       unsigned NumConcat = WidenVT.getVectorNumElements() /
1919                            InVT.getVectorNumElements();
1920       SDValue UndefVal = DAG.getUNDEF(InVT);
1921       SmallVector<SDValue, 16> Ops(NumConcat);
1922       for (unsigned i=0; i < NumOperands; ++i)
1923         Ops[i] = N->getOperand(i);
1924       for (unsigned i = NumOperands; i != NumConcat; ++i)
1925         Ops[i] = UndefVal;
1926       return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &Ops[0], NumConcat);
1927     }
1928   } else {
1929     InputWidened = true;
1930     if (WidenVT == TLI.getTypeToTransformTo(*DAG.getContext(), InVT)) {
1931       // The inputs and the result are widen to the same value.
1932       unsigned i;
1933       for (i=1; i < NumOperands; ++i)
1934         if (N->getOperand(i).getOpcode() != ISD::UNDEF)
1935           break;
1936
1937       if (i == NumOperands)
1938         // Everything but the first operand is an UNDEF so just return the
1939         // widened first operand.
1940         return GetWidenedVector(N->getOperand(0));
1941
1942       if (NumOperands == 2) {
1943         // Replace concat of two operands with a shuffle.
1944         SmallVector<int, 16> MaskOps(WidenNumElts, -1);
1945         for (unsigned i = 0; i < NumInElts; ++i) {
1946           MaskOps[i] = i;
1947           MaskOps[i + NumInElts] = i + WidenNumElts;
1948         }
1949         return DAG.getVectorShuffle(WidenVT, dl,
1950                                     GetWidenedVector(N->getOperand(0)),
1951                                     GetWidenedVector(N->getOperand(1)),
1952                                     &MaskOps[0]);
1953       }
1954     }
1955   }
1956
1957   // Fall back to use extracts and build vector.
1958   EVT EltVT = WidenVT.getVectorElementType();
1959   SmallVector<SDValue, 16> Ops(WidenNumElts);
1960   unsigned Idx = 0;
1961   for (unsigned i=0; i < NumOperands; ++i) {
1962     SDValue InOp = N->getOperand(i);
1963     if (InputWidened)
1964       InOp = GetWidenedVector(InOp);
1965     for (unsigned j=0; j < NumInElts; ++j)
1966       Ops[Idx++] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
1967                                DAG.getConstant(j, TLI.getVectorIdxTy()));
1968   }
1969   SDValue UndefVal = DAG.getUNDEF(EltVT);
1970   for (; Idx < WidenNumElts; ++Idx)
1971     Ops[Idx] = UndefVal;
1972   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], WidenNumElts);
1973 }
1974
1975 SDValue DAGTypeLegalizer::WidenVecRes_CONVERT_RNDSAT(SDNode *N) {
1976   SDLoc dl(N);
1977   SDValue InOp  = N->getOperand(0);
1978   SDValue RndOp = N->getOperand(3);
1979   SDValue SatOp = N->getOperand(4);
1980
1981   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1982   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1983
1984   EVT InVT = InOp.getValueType();
1985   EVT InEltVT = InVT.getVectorElementType();
1986   EVT InWidenVT = EVT::getVectorVT(*DAG.getContext(), InEltVT, WidenNumElts);
1987
1988   SDValue DTyOp = DAG.getValueType(WidenVT);
1989   SDValue STyOp = DAG.getValueType(InWidenVT);
1990   ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
1991
1992   unsigned InVTNumElts = InVT.getVectorNumElements();
1993   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
1994     InOp = GetWidenedVector(InOp);
1995     InVT = InOp.getValueType();
1996     InVTNumElts = InVT.getVectorNumElements();
1997     if (InVTNumElts == WidenNumElts)
1998       return DAG.getConvertRndSat(WidenVT, dl, InOp, DTyOp, STyOp, RndOp,
1999                                   SatOp, CvtCode);
2000   }
2001
2002   if (TLI.isTypeLegal(InWidenVT)) {
2003     // Because the result and the input are different vector types, widening
2004     // the result could create a legal type but widening the input might make
2005     // it an illegal type that might lead to repeatedly splitting the input
2006     // and then widening it. To avoid this, we widen the input only if
2007     // it results in a legal type.
2008     if (WidenNumElts % InVTNumElts == 0) {
2009       // Widen the input and call convert on the widened input vector.
2010       unsigned NumConcat = WidenNumElts/InVTNumElts;
2011       SmallVector<SDValue, 16> Ops(NumConcat);
2012       Ops[0] = InOp;
2013       SDValue UndefVal = DAG.getUNDEF(InVT);
2014       for (unsigned i = 1; i != NumConcat; ++i)
2015         Ops[i] = UndefVal;
2016
2017       InOp = DAG.getNode(ISD::CONCAT_VECTORS, dl, InWidenVT, &Ops[0],NumConcat);
2018       return DAG.getConvertRndSat(WidenVT, dl, InOp, DTyOp, STyOp, RndOp,
2019                                   SatOp, CvtCode);
2020     }
2021
2022     if (InVTNumElts % WidenNumElts == 0) {
2023       // Extract the input and convert the shorten input vector.
2024       InOp = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, InWidenVT, InOp,
2025                          DAG.getConstant(0, TLI.getVectorIdxTy()));
2026       return DAG.getConvertRndSat(WidenVT, dl, InOp, DTyOp, STyOp, RndOp,
2027                                   SatOp, CvtCode);
2028     }
2029   }
2030
2031   // Otherwise unroll into some nasty scalar code and rebuild the vector.
2032   SmallVector<SDValue, 16> Ops(WidenNumElts);
2033   EVT EltVT = WidenVT.getVectorElementType();
2034   DTyOp = DAG.getValueType(EltVT);
2035   STyOp = DAG.getValueType(InEltVT);
2036
2037   unsigned MinElts = std::min(InVTNumElts, WidenNumElts);
2038   unsigned i;
2039   for (i=0; i < MinElts; ++i) {
2040     SDValue ExtVal = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
2041                                  DAG.getConstant(i, TLI.getVectorIdxTy()));
2042     Ops[i] = DAG.getConvertRndSat(WidenVT, dl, ExtVal, DTyOp, STyOp, RndOp,
2043                                   SatOp, CvtCode);
2044   }
2045
2046   SDValue UndefVal = DAG.getUNDEF(EltVT);
2047   for (; i < WidenNumElts; ++i)
2048     Ops[i] = UndefVal;
2049
2050   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], WidenNumElts);
2051 }
2052
2053 SDValue DAGTypeLegalizer::WidenVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
2054   EVT      VT = N->getValueType(0);
2055   EVT      WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2056   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2057   SDValue  InOp = N->getOperand(0);
2058   SDValue  Idx  = N->getOperand(1);
2059   SDLoc dl(N);
2060
2061   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2062     InOp = GetWidenedVector(InOp);
2063
2064   EVT InVT = InOp.getValueType();
2065
2066   // Check if we can just return the input vector after widening.
2067   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
2068   if (IdxVal == 0 && InVT == WidenVT)
2069     return InOp;
2070
2071   // Check if we can extract from the vector.
2072   unsigned InNumElts = InVT.getVectorNumElements();
2073   if (IdxVal % WidenNumElts == 0 && IdxVal + WidenNumElts < InNumElts)
2074     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, WidenVT, InOp, Idx);
2075
2076   // We could try widening the input to the right length but for now, extract
2077   // the original elements, fill the rest with undefs and build a vector.
2078   SmallVector<SDValue, 16> Ops(WidenNumElts);
2079   EVT EltVT = VT.getVectorElementType();
2080   unsigned NumElts = VT.getVectorNumElements();
2081   unsigned i;
2082   for (i=0; i < NumElts; ++i)
2083     Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2084                          DAG.getConstant(IdxVal+i, TLI.getVectorIdxTy()));
2085
2086   SDValue UndefVal = DAG.getUNDEF(EltVT);
2087   for (; i < WidenNumElts; ++i)
2088     Ops[i] = UndefVal;
2089   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], WidenNumElts);
2090 }
2091
2092 SDValue DAGTypeLegalizer::WidenVecRes_INSERT_VECTOR_ELT(SDNode *N) {
2093   SDValue InOp = GetWidenedVector(N->getOperand(0));
2094   return DAG.getNode(ISD::INSERT_VECTOR_ELT, SDLoc(N),
2095                      InOp.getValueType(), InOp,
2096                      N->getOperand(1), N->getOperand(2));
2097 }
2098
2099 SDValue DAGTypeLegalizer::WidenVecRes_LOAD(SDNode *N) {
2100   LoadSDNode *LD = cast<LoadSDNode>(N);
2101   ISD::LoadExtType ExtType = LD->getExtensionType();
2102
2103   SDValue Result;
2104   SmallVector<SDValue, 16> LdChain;  // Chain for the series of load
2105   if (ExtType != ISD::NON_EXTLOAD)
2106     Result = GenWidenVectorExtLoads(LdChain, LD, ExtType);
2107   else
2108     Result = GenWidenVectorLoads(LdChain, LD);
2109
2110   // If we generate a single load, we can use that for the chain.  Otherwise,
2111   // build a factor node to remember the multiple loads are independent and
2112   // chain to that.
2113   SDValue NewChain;
2114   if (LdChain.size() == 1)
2115     NewChain = LdChain[0];
2116   else
2117     NewChain = DAG.getNode(ISD::TokenFactor, SDLoc(LD), MVT::Other,
2118                            &LdChain[0], LdChain.size());
2119
2120   // Modified the chain - switch anything that used the old chain to use
2121   // the new one.
2122   ReplaceValueWith(SDValue(N, 1), NewChain);
2123
2124   return Result;
2125 }
2126
2127 SDValue DAGTypeLegalizer::WidenVecRes_SCALAR_TO_VECTOR(SDNode *N) {
2128   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2129   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N),
2130                      WidenVT, N->getOperand(0));
2131 }
2132
2133 SDValue DAGTypeLegalizer::WidenVecRes_SELECT(SDNode *N) {
2134   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2135   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2136
2137   SDValue Cond1 = N->getOperand(0);
2138   EVT CondVT = Cond1.getValueType();
2139   if (CondVT.isVector()) {
2140     EVT CondEltVT = CondVT.getVectorElementType();
2141     EVT CondWidenVT =  EVT::getVectorVT(*DAG.getContext(),
2142                                         CondEltVT, WidenNumElts);
2143     if (getTypeAction(CondVT) == TargetLowering::TypeWidenVector)
2144       Cond1 = GetWidenedVector(Cond1);
2145
2146     if (Cond1.getValueType() != CondWidenVT)
2147       Cond1 = ModifyToType(Cond1, CondWidenVT);
2148   }
2149
2150   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
2151   SDValue InOp2 = GetWidenedVector(N->getOperand(2));
2152   assert(InOp1.getValueType() == WidenVT && InOp2.getValueType() == WidenVT);
2153   return DAG.getNode(N->getOpcode(), SDLoc(N),
2154                      WidenVT, Cond1, InOp1, InOp2);
2155 }
2156
2157 SDValue DAGTypeLegalizer::WidenVecRes_SELECT_CC(SDNode *N) {
2158   SDValue InOp1 = GetWidenedVector(N->getOperand(2));
2159   SDValue InOp2 = GetWidenedVector(N->getOperand(3));
2160   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
2161                      InOp1.getValueType(), N->getOperand(0),
2162                      N->getOperand(1), InOp1, InOp2, N->getOperand(4));
2163 }
2164
2165 SDValue DAGTypeLegalizer::WidenVecRes_SETCC(SDNode *N) {
2166   assert(N->getValueType(0).isVector() ==
2167          N->getOperand(0).getValueType().isVector() &&
2168          "Scalar/Vector type mismatch");
2169   if (N->getValueType(0).isVector()) return WidenVecRes_VSETCC(N);
2170
2171   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2172   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2173   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2174   return DAG.getNode(ISD::SETCC, SDLoc(N), WidenVT,
2175                      InOp1, InOp2, N->getOperand(2));
2176 }
2177
2178 SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) {
2179  EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2180  return DAG.getUNDEF(WidenVT);
2181 }
2182
2183 SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N) {
2184   EVT VT = N->getValueType(0);
2185   SDLoc dl(N);
2186
2187   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2188   unsigned NumElts = VT.getVectorNumElements();
2189   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2190
2191   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2192   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2193
2194   // Adjust mask based on new input vector length.
2195   SmallVector<int, 16> NewMask;
2196   for (unsigned i = 0; i != NumElts; ++i) {
2197     int Idx = N->getMaskElt(i);
2198     if (Idx < (int)NumElts)
2199       NewMask.push_back(Idx);
2200     else
2201       NewMask.push_back(Idx - NumElts + WidenNumElts);
2202   }
2203   for (unsigned i = NumElts; i != WidenNumElts; ++i)
2204     NewMask.push_back(-1);
2205   return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, &NewMask[0]);
2206 }
2207
2208 SDValue DAGTypeLegalizer::WidenVecRes_VSETCC(SDNode *N) {
2209   assert(N->getValueType(0).isVector() &&
2210          N->getOperand(0).getValueType().isVector() &&
2211          "Operands must be vectors");
2212   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2213   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2214
2215   SDValue InOp1 = N->getOperand(0);
2216   EVT InVT = InOp1.getValueType();
2217   assert(InVT.isVector() && "can not widen non vector type");
2218   EVT WidenInVT = EVT::getVectorVT(*DAG.getContext(),
2219                                    InVT.getVectorElementType(), WidenNumElts);
2220   InOp1 = GetWidenedVector(InOp1);
2221   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2222
2223   // Assume that the input and output will be widen appropriately.  If not,
2224   // we will have to unroll it at some point.
2225   assert(InOp1.getValueType() == WidenInVT &&
2226          InOp2.getValueType() == WidenInVT &&
2227          "Input not widened to expected type!");
2228   (void)WidenInVT;
2229   return DAG.getNode(ISD::SETCC, SDLoc(N),
2230                      WidenVT, InOp1, InOp2, N->getOperand(2));
2231 }
2232
2233
2234 //===----------------------------------------------------------------------===//
2235 // Widen Vector Operand
2236 //===----------------------------------------------------------------------===//
2237 bool DAGTypeLegalizer::WidenVectorOperand(SDNode *N, unsigned OpNo) {
2238   DEBUG(dbgs() << "Widen node operand " << OpNo << ": ";
2239         N->dump(&DAG);
2240         dbgs() << "\n");
2241   SDValue Res = SDValue();
2242
2243   // See if the target wants to custom widen this node.
2244   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
2245     return false;
2246
2247   switch (N->getOpcode()) {
2248   default:
2249 #ifndef NDEBUG
2250     dbgs() << "WidenVectorOperand op #" << OpNo << ": ";
2251     N->dump(&DAG);
2252     dbgs() << "\n";
2253 #endif
2254     llvm_unreachable("Do not know how to widen this operator's operand!");
2255
2256   case ISD::BITCAST:            Res = WidenVecOp_BITCAST(N); break;
2257   case ISD::CONCAT_VECTORS:     Res = WidenVecOp_CONCAT_VECTORS(N); break;
2258   case ISD::EXTRACT_SUBVECTOR:  Res = WidenVecOp_EXTRACT_SUBVECTOR(N); break;
2259   case ISD::EXTRACT_VECTOR_ELT: Res = WidenVecOp_EXTRACT_VECTOR_ELT(N); break;
2260   case ISD::STORE:              Res = WidenVecOp_STORE(N); break;
2261   case ISD::SETCC:              Res = WidenVecOp_SETCC(N); break;
2262
2263   case ISD::FP_EXTEND:
2264   case ISD::FP_TO_SINT:
2265   case ISD::FP_TO_UINT:
2266   case ISD::SINT_TO_FP:
2267   case ISD::UINT_TO_FP:
2268   case ISD::TRUNCATE:
2269   case ISD::SIGN_EXTEND:
2270   case ISD::ZERO_EXTEND:
2271   case ISD::ANY_EXTEND:
2272     Res = WidenVecOp_Convert(N);
2273     break;
2274   }
2275
2276   // If Res is null, the sub-method took care of registering the result.
2277   if (!Res.getNode()) return false;
2278
2279   // If the result is N, the sub-method updated N in place.  Tell the legalizer
2280   // core about this.
2281   if (Res.getNode() == N)
2282     return true;
2283
2284
2285   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
2286          "Invalid operand expansion");
2287
2288   ReplaceValueWith(SDValue(N, 0), Res);
2289   return false;
2290 }
2291
2292 SDValue DAGTypeLegalizer::WidenVecOp_Convert(SDNode *N) {
2293   // Since the result is legal and the input is illegal, it is unlikely
2294   // that we can fix the input to a legal type so unroll the convert
2295   // into some scalar code and create a nasty build vector.
2296   EVT VT = N->getValueType(0);
2297   EVT EltVT = VT.getVectorElementType();
2298   SDLoc dl(N);
2299   unsigned NumElts = VT.getVectorNumElements();
2300   SDValue InOp = N->getOperand(0);
2301   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2302     InOp = GetWidenedVector(InOp);
2303   EVT InVT = InOp.getValueType();
2304   EVT InEltVT = InVT.getVectorElementType();
2305
2306   unsigned Opcode = N->getOpcode();
2307   SmallVector<SDValue, 16> Ops(NumElts);
2308   for (unsigned i=0; i < NumElts; ++i)
2309     Ops[i] = DAG.getNode(Opcode, dl, EltVT,
2310                          DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
2311                                      DAG.getConstant(i, TLI.getVectorIdxTy())));
2312
2313   return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElts);
2314 }
2315
2316 SDValue DAGTypeLegalizer::WidenVecOp_BITCAST(SDNode *N) {
2317   EVT VT = N->getValueType(0);
2318   SDValue InOp = GetWidenedVector(N->getOperand(0));
2319   EVT InWidenVT = InOp.getValueType();
2320   SDLoc dl(N);
2321
2322   // Check if we can convert between two legal vector types and extract.
2323   unsigned InWidenSize = InWidenVT.getSizeInBits();
2324   unsigned Size = VT.getSizeInBits();
2325   // x86mmx is not an acceptable vector element type, so don't try.
2326   if (InWidenSize % Size == 0 && !VT.isVector() && VT != MVT::x86mmx) {
2327     unsigned NewNumElts = InWidenSize / Size;
2328     EVT NewVT = EVT::getVectorVT(*DAG.getContext(), VT, NewNumElts);
2329     if (TLI.isTypeLegal(NewVT)) {
2330       SDValue BitOp = DAG.getNode(ISD::BITCAST, dl, NewVT, InOp);
2331       return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, VT, BitOp,
2332                          DAG.getConstant(0, TLI.getVectorIdxTy()));
2333     }
2334   }
2335
2336   return CreateStackStoreLoad(InOp, VT);
2337 }
2338
2339 SDValue DAGTypeLegalizer::WidenVecOp_CONCAT_VECTORS(SDNode *N) {
2340   // If the input vector is not legal, it is likely that we will not find a
2341   // legal vector of the same size. Replace the concatenate vector with a
2342   // nasty build vector.
2343   EVT VT = N->getValueType(0);
2344   EVT EltVT = VT.getVectorElementType();
2345   SDLoc dl(N);
2346   unsigned NumElts = VT.getVectorNumElements();
2347   SmallVector<SDValue, 16> Ops(NumElts);
2348
2349   EVT InVT = N->getOperand(0).getValueType();
2350   unsigned NumInElts = InVT.getVectorNumElements();
2351
2352   unsigned Idx = 0;
2353   unsigned NumOperands = N->getNumOperands();
2354   for (unsigned i=0; i < NumOperands; ++i) {
2355     SDValue InOp = N->getOperand(i);
2356     if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2357       InOp = GetWidenedVector(InOp);
2358     for (unsigned j=0; j < NumInElts; ++j)
2359       Ops[Idx++] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2360                                DAG.getConstant(j, TLI.getVectorIdxTy()));
2361   }
2362   return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElts);
2363 }
2364
2365 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
2366   SDValue InOp = GetWidenedVector(N->getOperand(0));
2367   return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(N),
2368                      N->getValueType(0), InOp, N->getOperand(1));
2369 }
2370
2371 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
2372   SDValue InOp = GetWidenedVector(N->getOperand(0));
2373   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
2374                      N->getValueType(0), InOp, N->getOperand(1));
2375 }
2376
2377 SDValue DAGTypeLegalizer::WidenVecOp_STORE(SDNode *N) {
2378   // We have to widen the value but we want only to store the original
2379   // vector type.
2380   StoreSDNode *ST = cast<StoreSDNode>(N);
2381
2382   SmallVector<SDValue, 16> StChain;
2383   if (ST->isTruncatingStore())
2384     GenWidenVectorTruncStores(StChain, ST);
2385   else
2386     GenWidenVectorStores(StChain, ST);
2387
2388   if (StChain.size() == 1)
2389     return StChain[0];
2390   else
2391     return DAG.getNode(ISD::TokenFactor, SDLoc(ST),
2392                        MVT::Other,&StChain[0],StChain.size());
2393 }
2394
2395 SDValue DAGTypeLegalizer::WidenVecOp_SETCC(SDNode *N) {
2396   SDValue InOp0 = GetWidenedVector(N->getOperand(0));
2397   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
2398   SDLoc dl(N);
2399
2400   // WARNING: In this code we widen the compare instruction with garbage.
2401   // This garbage may contain denormal floats which may be slow. Is this a real
2402   // concern ? Should we zero the unused lanes if this is a float compare ?
2403
2404   // Get a new SETCC node to compare the newly widened operands.
2405   // Only some of the compared elements are legal.
2406   EVT SVT = TLI.getSetCCResultType(*DAG.getContext(), InOp0.getValueType());
2407   SDValue WideSETCC = DAG.getNode(ISD::SETCC, SDLoc(N),
2408                      SVT, InOp0, InOp1, N->getOperand(2));
2409
2410   // Extract the needed results from the result vector.
2411   EVT ResVT = EVT::getVectorVT(*DAG.getContext(),
2412                                SVT.getVectorElementType(),
2413                                N->getValueType(0).getVectorNumElements());
2414   SDValue CC = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl,
2415                            ResVT, WideSETCC, DAG.getConstant(0,
2416                                              TLI.getVectorIdxTy()));
2417
2418   return PromoteTargetBoolean(CC, N->getValueType(0));
2419 }
2420
2421
2422 //===----------------------------------------------------------------------===//
2423 // Vector Widening Utilities
2424 //===----------------------------------------------------------------------===//
2425
2426 // Utility function to find the type to chop up a widen vector for load/store
2427 //  TLI:       Target lowering used to determine legal types.
2428 //  Width:     Width left need to load/store.
2429 //  WidenVT:   The widen vector type to load to/store from
2430 //  Align:     If 0, don't allow use of a wider type
2431 //  WidenEx:   If Align is not 0, the amount additional we can load/store from.
2432
2433 static EVT FindMemType(SelectionDAG& DAG, const TargetLowering &TLI,
2434                        unsigned Width, EVT WidenVT,
2435                        unsigned Align = 0, unsigned WidenEx = 0) {
2436   EVT WidenEltVT = WidenVT.getVectorElementType();
2437   unsigned WidenWidth = WidenVT.getSizeInBits();
2438   unsigned WidenEltWidth = WidenEltVT.getSizeInBits();
2439   unsigned AlignInBits = Align*8;
2440
2441   // If we have one element to load/store, return it.
2442   EVT RetVT = WidenEltVT;
2443   if (Width == WidenEltWidth)
2444     return RetVT;
2445
2446   // See if there is larger legal integer than the element type to load/store
2447   unsigned VT;
2448   for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE;
2449        VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) {
2450     EVT MemVT((MVT::SimpleValueType) VT);
2451     unsigned MemVTWidth = MemVT.getSizeInBits();
2452     if (MemVT.getSizeInBits() <= WidenEltWidth)
2453       break;
2454     if (TLI.isTypeLegal(MemVT) && (WidenWidth % MemVTWidth) == 0 &&
2455         isPowerOf2_32(WidenWidth / MemVTWidth) &&
2456         (MemVTWidth <= Width ||
2457          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
2458       RetVT = MemVT;
2459       break;
2460     }
2461   }
2462
2463   // See if there is a larger vector type to load/store that has the same vector
2464   // element type and is evenly divisible with the WidenVT.
2465   for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE;
2466        VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) {
2467     EVT MemVT = (MVT::SimpleValueType) VT;
2468     unsigned MemVTWidth = MemVT.getSizeInBits();
2469     if (TLI.isTypeLegal(MemVT) && WidenEltVT == MemVT.getVectorElementType() &&
2470         (WidenWidth % MemVTWidth) == 0 &&
2471         isPowerOf2_32(WidenWidth / MemVTWidth) &&
2472         (MemVTWidth <= Width ||
2473          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
2474       if (RetVT.getSizeInBits() < MemVTWidth || MemVT == WidenVT)
2475         return MemVT;
2476     }
2477   }
2478
2479   return RetVT;
2480 }
2481
2482 // Builds a vector type from scalar loads
2483 //  VecTy: Resulting Vector type
2484 //  LDOps: Load operators to build a vector type
2485 //  [Start,End) the list of loads to use.
2486 static SDValue BuildVectorFromScalar(SelectionDAG& DAG, EVT VecTy,
2487                                      SmallVectorImpl<SDValue> &LdOps,
2488                                      unsigned Start, unsigned End) {
2489   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2490   SDLoc dl(LdOps[Start]);
2491   EVT LdTy = LdOps[Start].getValueType();
2492   unsigned Width = VecTy.getSizeInBits();
2493   unsigned NumElts = Width / LdTy.getSizeInBits();
2494   EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), LdTy, NumElts);
2495
2496   unsigned Idx = 1;
2497   SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT,LdOps[Start]);
2498
2499   for (unsigned i = Start + 1; i != End; ++i) {
2500     EVT NewLdTy = LdOps[i].getValueType();
2501     if (NewLdTy != LdTy) {
2502       NumElts = Width / NewLdTy.getSizeInBits();
2503       NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewLdTy, NumElts);
2504       VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, VecOp);
2505       // Readjust position and vector position based on new load type
2506       Idx = Idx * LdTy.getSizeInBits() / NewLdTy.getSizeInBits();
2507       LdTy = NewLdTy;
2508     }
2509     VecOp = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NewVecVT, VecOp, LdOps[i],
2510                         DAG.getConstant(Idx++, TLI.getVectorIdxTy()));
2511   }
2512   return DAG.getNode(ISD::BITCAST, dl, VecTy, VecOp);
2513 }
2514
2515 SDValue DAGTypeLegalizer::GenWidenVectorLoads(SmallVectorImpl<SDValue> &LdChain,
2516                                               LoadSDNode *LD) {
2517   // The strategy assumes that we can efficiently load powers of two widths.
2518   // The routines chops the vector into the largest vector loads with the same
2519   // element type or scalar loads and then recombines it to the widen vector
2520   // type.
2521   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
2522   unsigned WidenWidth = WidenVT.getSizeInBits();
2523   EVT LdVT    = LD->getMemoryVT();
2524   SDLoc dl(LD);
2525   assert(LdVT.isVector() && WidenVT.isVector());
2526   assert(LdVT.getVectorElementType() == WidenVT.getVectorElementType());
2527
2528   // Load information
2529   SDValue   Chain = LD->getChain();
2530   SDValue   BasePtr = LD->getBasePtr();
2531   unsigned  Align    = LD->getAlignment();
2532   bool      isVolatile = LD->isVolatile();
2533   bool      isNonTemporal = LD->isNonTemporal();
2534   bool      isInvariant = LD->isInvariant();
2535
2536   int LdWidth = LdVT.getSizeInBits();
2537   int WidthDiff = WidenWidth - LdWidth;          // Difference
2538   unsigned LdAlign = (isVolatile) ? 0 : Align; // Allow wider loads
2539
2540   // Find the vector type that can load from.
2541   EVT NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
2542   int NewVTWidth = NewVT.getSizeInBits();
2543   SDValue LdOp = DAG.getLoad(NewVT, dl, Chain, BasePtr, LD->getPointerInfo(),
2544                              isVolatile, isNonTemporal, isInvariant, Align);
2545   LdChain.push_back(LdOp.getValue(1));
2546
2547   // Check if we can load the element with one instruction
2548   if (LdWidth <= NewVTWidth) {
2549     if (!NewVT.isVector()) {
2550       unsigned NumElts = WidenWidth / NewVTWidth;
2551       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
2552       SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT, LdOp);
2553       return DAG.getNode(ISD::BITCAST, dl, WidenVT, VecOp);
2554     }
2555     if (NewVT == WidenVT)
2556       return LdOp;
2557
2558     assert(WidenWidth % NewVTWidth == 0);
2559     unsigned NumConcat = WidenWidth / NewVTWidth;
2560     SmallVector<SDValue, 16> ConcatOps(NumConcat);
2561     SDValue UndefVal = DAG.getUNDEF(NewVT);
2562     ConcatOps[0] = LdOp;
2563     for (unsigned i = 1; i != NumConcat; ++i)
2564       ConcatOps[i] = UndefVal;
2565     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &ConcatOps[0],
2566                        NumConcat);
2567   }
2568
2569   // Load vector by using multiple loads from largest vector to scalar
2570   SmallVector<SDValue, 16> LdOps;
2571   LdOps.push_back(LdOp);
2572
2573   LdWidth -= NewVTWidth;
2574   unsigned Offset = 0;
2575
2576   while (LdWidth > 0) {
2577     unsigned Increment = NewVTWidth / 8;
2578     Offset += Increment;
2579     BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
2580                           DAG.getIntPtrConstant(Increment));
2581
2582     SDValue L;
2583     if (LdWidth < NewVTWidth) {
2584       // Our current type we are using is too large, find a better size
2585       NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
2586       NewVTWidth = NewVT.getSizeInBits();
2587       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
2588                       LD->getPointerInfo().getWithOffset(Offset), isVolatile,
2589                       isNonTemporal, isInvariant, MinAlign(Align, Increment));
2590       LdChain.push_back(L.getValue(1));
2591       if (L->getValueType(0).isVector()) {
2592         SmallVector<SDValue, 16> Loads;
2593         Loads.push_back(L);
2594         unsigned size = L->getValueSizeInBits(0);
2595         while (size < LdOp->getValueSizeInBits(0)) {
2596           Loads.push_back(DAG.getUNDEF(L->getValueType(0)));
2597           size += L->getValueSizeInBits(0);
2598         }
2599         L = DAG.getNode(ISD::CONCAT_VECTORS, dl, LdOp->getValueType(0),
2600                         &Loads[0], Loads.size());
2601       }
2602     } else {
2603       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
2604                       LD->getPointerInfo().getWithOffset(Offset), isVolatile,
2605                       isNonTemporal, isInvariant, MinAlign(Align, Increment));
2606       LdChain.push_back(L.getValue(1));
2607     }
2608
2609     LdOps.push_back(L);
2610
2611
2612     LdWidth -= NewVTWidth;
2613   }
2614
2615   // Build the vector from the loads operations
2616   unsigned End = LdOps.size();
2617   if (!LdOps[0].getValueType().isVector())
2618     // All the loads are scalar loads.
2619     return BuildVectorFromScalar(DAG, WidenVT, LdOps, 0, End);
2620
2621   // If the load contains vectors, build the vector using concat vector.
2622   // All of the vectors used to loads are power of 2 and the scalars load
2623   // can be combined to make a power of 2 vector.
2624   SmallVector<SDValue, 16> ConcatOps(End);
2625   int i = End - 1;
2626   int Idx = End;
2627   EVT LdTy = LdOps[i].getValueType();
2628   // First combine the scalar loads to a vector
2629   if (!LdTy.isVector())  {
2630     for (--i; i >= 0; --i) {
2631       LdTy = LdOps[i].getValueType();
2632       if (LdTy.isVector())
2633         break;
2634     }
2635     ConcatOps[--Idx] = BuildVectorFromScalar(DAG, LdTy, LdOps, i+1, End);
2636   }
2637   ConcatOps[--Idx] = LdOps[i];
2638   for (--i; i >= 0; --i) {
2639     EVT NewLdTy = LdOps[i].getValueType();
2640     if (NewLdTy != LdTy) {
2641       // Create a larger vector
2642       ConcatOps[End-1] = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewLdTy,
2643                                      &ConcatOps[Idx], End - Idx);
2644       Idx = End - 1;
2645       LdTy = NewLdTy;
2646     }
2647     ConcatOps[--Idx] = LdOps[i];
2648   }
2649
2650   if (WidenWidth == LdTy.getSizeInBits()*(End - Idx))
2651     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
2652                        &ConcatOps[Idx], End - Idx);
2653
2654   // We need to fill the rest with undefs to build the vector
2655   unsigned NumOps = WidenWidth / LdTy.getSizeInBits();
2656   SmallVector<SDValue, 16> WidenOps(NumOps);
2657   SDValue UndefVal = DAG.getUNDEF(LdTy);
2658   {
2659     unsigned i = 0;
2660     for (; i != End-Idx; ++i)
2661       WidenOps[i] = ConcatOps[Idx+i];
2662     for (; i != NumOps; ++i)
2663       WidenOps[i] = UndefVal;
2664   }
2665   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &WidenOps[0],NumOps);
2666 }
2667
2668 SDValue
2669 DAGTypeLegalizer::GenWidenVectorExtLoads(SmallVectorImpl<SDValue> &LdChain,
2670                                          LoadSDNode *LD,
2671                                          ISD::LoadExtType ExtType) {
2672   // For extension loads, it may not be more efficient to chop up the vector
2673   // and then extended it.  Instead, we unroll the load and build a new vector.
2674   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
2675   EVT LdVT    = LD->getMemoryVT();
2676   SDLoc dl(LD);
2677   assert(LdVT.isVector() && WidenVT.isVector());
2678
2679   // Load information
2680   SDValue   Chain = LD->getChain();
2681   SDValue   BasePtr = LD->getBasePtr();
2682   unsigned  Align    = LD->getAlignment();
2683   bool      isVolatile = LD->isVolatile();
2684   bool      isNonTemporal = LD->isNonTemporal();
2685
2686   EVT EltVT = WidenVT.getVectorElementType();
2687   EVT LdEltVT = LdVT.getVectorElementType();
2688   unsigned NumElts = LdVT.getVectorNumElements();
2689
2690   // Load each element and widen
2691   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2692   SmallVector<SDValue, 16> Ops(WidenNumElts);
2693   unsigned Increment = LdEltVT.getSizeInBits() / 8;
2694   Ops[0] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, BasePtr,
2695                           LD->getPointerInfo(),
2696                           LdEltVT, isVolatile, isNonTemporal, Align);
2697   LdChain.push_back(Ops[0].getValue(1));
2698   unsigned i = 0, Offset = Increment;
2699   for (i=1; i < NumElts; ++i, Offset += Increment) {
2700     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
2701                                      BasePtr, DAG.getIntPtrConstant(Offset));
2702     Ops[i] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, NewBasePtr,
2703                             LD->getPointerInfo().getWithOffset(Offset), LdEltVT,
2704                             isVolatile, isNonTemporal, Align);
2705     LdChain.push_back(Ops[i].getValue(1));
2706   }
2707
2708   // Fill the rest with undefs
2709   SDValue UndefVal = DAG.getUNDEF(EltVT);
2710   for (; i != WidenNumElts; ++i)
2711     Ops[i] = UndefVal;
2712
2713   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], Ops.size());
2714 }
2715
2716
2717 void DAGTypeLegalizer::GenWidenVectorStores(SmallVectorImpl<SDValue> &StChain,
2718                                             StoreSDNode *ST) {
2719   // The strategy assumes that we can efficiently store powers of two widths.
2720   // The routines chops the vector into the largest vector stores with the same
2721   // element type or scalar stores.
2722   SDValue  Chain = ST->getChain();
2723   SDValue  BasePtr = ST->getBasePtr();
2724   unsigned Align = ST->getAlignment();
2725   bool     isVolatile = ST->isVolatile();
2726   bool     isNonTemporal = ST->isNonTemporal();
2727   SDValue  ValOp = GetWidenedVector(ST->getValue());
2728   SDLoc dl(ST);
2729
2730   EVT StVT = ST->getMemoryVT();
2731   unsigned StWidth = StVT.getSizeInBits();
2732   EVT ValVT = ValOp.getValueType();
2733   unsigned ValWidth = ValVT.getSizeInBits();
2734   EVT ValEltVT = ValVT.getVectorElementType();
2735   unsigned ValEltWidth = ValEltVT.getSizeInBits();
2736   assert(StVT.getVectorElementType() == ValEltVT);
2737
2738   int Idx = 0;          // current index to store
2739   unsigned Offset = 0;  // offset from base to store
2740   while (StWidth != 0) {
2741     // Find the largest vector type we can store with
2742     EVT NewVT = FindMemType(DAG, TLI, StWidth, ValVT);
2743     unsigned NewVTWidth = NewVT.getSizeInBits();
2744     unsigned Increment = NewVTWidth / 8;
2745     if (NewVT.isVector()) {
2746       unsigned NumVTElts = NewVT.getVectorNumElements();
2747       do {
2748         SDValue EOp = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, NewVT, ValOp,
2749                                    DAG.getConstant(Idx, TLI.getVectorIdxTy()));
2750         StChain.push_back(DAG.getStore(Chain, dl, EOp, BasePtr,
2751                                     ST->getPointerInfo().getWithOffset(Offset),
2752                                        isVolatile, isNonTemporal,
2753                                        MinAlign(Align, Offset)));
2754         StWidth -= NewVTWidth;
2755         Offset += Increment;
2756         Idx += NumVTElts;
2757         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
2758                               DAG.getIntPtrConstant(Increment));
2759       } while (StWidth != 0 && StWidth >= NewVTWidth);
2760     } else {
2761       // Cast the vector to the scalar type we can store
2762       unsigned NumElts = ValWidth / NewVTWidth;
2763       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
2764       SDValue VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, ValOp);
2765       // Readjust index position based on new vector type
2766       Idx = Idx * ValEltWidth / NewVTWidth;
2767       do {
2768         SDValue EOp = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, NewVT, VecOp,
2769                       DAG.getConstant(Idx++, TLI.getVectorIdxTy()));
2770         StChain.push_back(DAG.getStore(Chain, dl, EOp, BasePtr,
2771                                     ST->getPointerInfo().getWithOffset(Offset),
2772                                        isVolatile, isNonTemporal,
2773                                        MinAlign(Align, Offset)));
2774         StWidth -= NewVTWidth;
2775         Offset += Increment;
2776         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
2777                               DAG.getIntPtrConstant(Increment));
2778       } while (StWidth != 0 && StWidth >= NewVTWidth);
2779       // Restore index back to be relative to the original widen element type
2780       Idx = Idx * NewVTWidth / ValEltWidth;
2781     }
2782   }
2783 }
2784
2785 void
2786 DAGTypeLegalizer::GenWidenVectorTruncStores(SmallVectorImpl<SDValue> &StChain,
2787                                             StoreSDNode *ST) {
2788   // For extension loads, it may not be more efficient to truncate the vector
2789   // and then store it.  Instead, we extract each element and then store it.
2790   SDValue  Chain = ST->getChain();
2791   SDValue  BasePtr = ST->getBasePtr();
2792   unsigned Align = ST->getAlignment();
2793   bool     isVolatile = ST->isVolatile();
2794   bool     isNonTemporal = ST->isNonTemporal();
2795   SDValue  ValOp = GetWidenedVector(ST->getValue());
2796   SDLoc dl(ST);
2797
2798   EVT StVT = ST->getMemoryVT();
2799   EVT ValVT = ValOp.getValueType();
2800
2801   // It must be true that we the widen vector type is bigger than where
2802   // we need to store.
2803   assert(StVT.isVector() && ValOp.getValueType().isVector());
2804   assert(StVT.bitsLT(ValOp.getValueType()));
2805
2806   // For truncating stores, we can not play the tricks of chopping legal
2807   // vector types and bit cast it to the right type.  Instead, we unroll
2808   // the store.
2809   EVT StEltVT  = StVT.getVectorElementType();
2810   EVT ValEltVT = ValVT.getVectorElementType();
2811   unsigned Increment = ValEltVT.getSizeInBits() / 8;
2812   unsigned NumElts = StVT.getVectorNumElements();
2813   SDValue EOp = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
2814                             DAG.getConstant(0, TLI.getVectorIdxTy()));
2815   StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, BasePtr,
2816                                       ST->getPointerInfo(), StEltVT,
2817                                       isVolatile, isNonTemporal, Align));
2818   unsigned Offset = Increment;
2819   for (unsigned i=1; i < NumElts; ++i, Offset += Increment) {
2820     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
2821                                      BasePtr, DAG.getIntPtrConstant(Offset));
2822     SDValue EOp = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
2823                             DAG.getConstant(0, TLI.getVectorIdxTy()));
2824     StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, NewBasePtr,
2825                                       ST->getPointerInfo().getWithOffset(Offset),
2826                                         StEltVT, isVolatile, isNonTemporal,
2827                                         MinAlign(Align, Offset)));
2828   }
2829 }
2830
2831 /// Modifies a vector input (widen or narrows) to a vector of NVT.  The
2832 /// input vector must have the same element type as NVT.
2833 SDValue DAGTypeLegalizer::ModifyToType(SDValue InOp, EVT NVT) {
2834   // Note that InOp might have been widened so it might already have
2835   // the right width or it might need be narrowed.
2836   EVT InVT = InOp.getValueType();
2837   assert(InVT.getVectorElementType() == NVT.getVectorElementType() &&
2838          "input and widen element type must match");
2839   SDLoc dl(InOp);
2840
2841   // Check if InOp already has the right width.
2842   if (InVT == NVT)
2843     return InOp;
2844
2845   unsigned InNumElts = InVT.getVectorNumElements();
2846   unsigned WidenNumElts = NVT.getVectorNumElements();
2847   if (WidenNumElts > InNumElts && WidenNumElts % InNumElts == 0) {
2848     unsigned NumConcat = WidenNumElts / InNumElts;
2849     SmallVector<SDValue, 16> Ops(NumConcat);
2850     SDValue UndefVal = DAG.getUNDEF(InVT);
2851     Ops[0] = InOp;
2852     for (unsigned i = 1; i != NumConcat; ++i)
2853       Ops[i] = UndefVal;
2854
2855     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, &Ops[0], NumConcat);
2856   }
2857
2858   if (WidenNumElts < InNumElts && InNumElts % WidenNumElts)
2859     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, NVT, InOp,
2860                        DAG.getConstant(0, TLI.getVectorIdxTy()));
2861
2862   // Fall back to extract and build.
2863   SmallVector<SDValue, 16> Ops(WidenNumElts);
2864   EVT EltVT = NVT.getVectorElementType();
2865   unsigned MinNumElts = std::min(WidenNumElts, InNumElts);
2866   unsigned Idx;
2867   for (Idx = 0; Idx < MinNumElts; ++Idx)
2868     Ops[Idx] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2869                            DAG.getConstant(Idx, TLI.getVectorIdxTy()));
2870
2871   SDValue UndefVal = DAG.getUNDEF(EltVT);
2872   for ( ; Idx < WidenNumElts; ++Idx)
2873     Ops[Idx] = UndefVal;
2874   return DAG.getNode(ISD::BUILD_VECTOR, dl, NVT, &Ops[0], WidenNumElts);
2875 }