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