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