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