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