lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

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