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