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