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