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