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