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 using namespace llvm;
  25
  26 //===----------------------------------------------------------------------===//
  27 //  Result Vector Scalarization: <1 x ty> -> ty.
  28 //===----------------------------------------------------------------------===//
  29
  30 void DAGTypeLegalizer::ScalarizeVectorResult(SDNode *N, unsigned ResNo) {
  31   DEBUG(cerr << "Scalarize node result " << ResNo << ": "; N->dump(&DAG);
  32         cerr << "\n");
  33   SDValue R = SDValue();
  34
  35   switch (N->getOpcode()) {
  36   default:
  37 #ifndef NDEBUG
  38     cerr << "ScalarizeVectorResult #" << ResNo << ": ";
  39     N->dump(&DAG); cerr << "\n";
  40 #endif
  41     assert(0 && "Do not know how to scalarize the result of this operator!");
  42     abort();
  43
  44   case ISD::BIT_CONVERT:    R = ScalarizeVecRes_BIT_CONVERT(N); break;
  45   case ISD::BUILD_VECTOR:   R = N->getOperand(0); break;
  46   case ISD::EXTRACT_SUBVECTOR: R = ScalarizeVecRes_EXTRACT_SUBVECTOR(N); break;
  47   case ISD::FPOWI:          R = ScalarizeVecRes_FPOWI(N); break;
  48   case ISD::INSERT_VECTOR_ELT: R = ScalarizeVecRes_INSERT_VECTOR_ELT(N); break;
  49   case ISD::LOAD:           R = ScalarizeVecRes_LOAD(cast<LoadSDNode>(N));break;
  50   case ISD::SELECT:         R = ScalarizeVecRes_SELECT(N); break;
  51   case ISD::UNDEF:          R = ScalarizeVecRes_UNDEF(N); break;
  52   case ISD::VECTOR_SHUFFLE: R = ScalarizeVecRes_VECTOR_SHUFFLE(N); break;
  53   case ISD::VSETCC:         R = ScalarizeVecRes_VSETCC(N); break;
  54
  55   case ISD::CTLZ:
  56   case ISD::CTPOP:
  57   case ISD::CTTZ:
  58   case ISD::FABS:
  59   case ISD::FCOS:
  60   case ISD::FNEG:
  61   case ISD::FP_TO_SINT:
  62   case ISD::FP_TO_UINT:
  63   case ISD::FSIN:
  64   case ISD::FSQRT:
  65   case ISD::FTRUNC:
  66   case ISD::FFLOOR:
  67   case ISD::FCEIL:
  68   case ISD::FRINT:
  69   case ISD::FNEARBYINT:
  70   case ISD::SINT_TO_FP:
  71   case ISD::TRUNCATE:
  72   case ISD::UINT_TO_FP: R = ScalarizeVecRes_UnaryOp(N); break;
  73
  74   case ISD::ADD:
  75   case ISD::AND:
  76   case ISD::FADD:
  77   case ISD::FDIV:
  78   case ISD::FMUL:
  79   case ISD::FPOW:
  80   case ISD::FREM:
  81   case ISD::FSUB:
  82   case ISD::MUL:
  83   case ISD::OR:
  84   case ISD::SDIV:
  85   case ISD::SREM:
  86   case ISD::SUB:
  87   case ISD::UDIV:
  88   case ISD::UREM:
  89   case ISD::XOR:  R = ScalarizeVecRes_BinOp(N); break;
  90   }
  91
  92   // If R is null, the sub-method took care of registering the result.
  93   if (R.getNode())
  94     SetScalarizedVector(SDValue(N, ResNo), R);
  95 }
  96
  97 SDValue DAGTypeLegalizer::ScalarizeVecRes_BinOp(SDNode *N) {
  98   SDValue LHS = GetScalarizedVector(N->getOperand(0));
  99   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 100   return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
 101 }
 102
 103 SDValue DAGTypeLegalizer::ScalarizeVecRes_BIT_CONVERT(SDNode *N) {
 104   MVT NewVT = N->getValueType(0).getVectorElementType();
 105   return DAG.getNode(ISD::BIT_CONVERT, NewVT, N->getOperand(0));
 106 }
 107
 108 SDValue DAGTypeLegalizer::ScalarizeVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
 109   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT,
 110                      N->getValueType(0).getVectorElementType(),
 111                      N->getOperand(0), N->getOperand(1));
 112 }
 113
 114 SDValue DAGTypeLegalizer::ScalarizeVecRes_FPOWI(SDNode *N) {
 115   SDValue Op = GetScalarizedVector(N->getOperand(0));
 116   return DAG.getNode(ISD::FPOWI, Op.getValueType(), Op, N->getOperand(1));
 117 }
 118
 119 SDValue DAGTypeLegalizer::ScalarizeVecRes_INSERT_VECTOR_ELT(SDNode *N) {
 120   // The value to insert may have a wider type than the vector element type,
 121   // so be sure to truncate it to the element type if necessary.
 122   SDValue Op = N->getOperand(1);
 123   MVT EltVT = N->getValueType(0).getVectorElementType();
 124   if (Op.getValueType() != EltVT)
 125     // FIXME: Can this happen for floating point types?
 126     Op = DAG.getNode(ISD::TRUNCATE, EltVT, Op);
 127   return Op;
 128 }
 129
 130 SDValue DAGTypeLegalizer::ScalarizeVecRes_LOAD(LoadSDNode *N) {
 131   assert(N->isUnindexed() && "Indexed vector load?");
 132
 133   SDValue Result = DAG.getLoad(ISD::UNINDEXED, N->getExtensionType(),
 134                                N->getValueType(0).getVectorElementType(),
 135                                N->getChain(), N->getBasePtr(),
 136                                DAG.getNode(ISD::UNDEF,
 137                                            N->getBasePtr().getValueType()),
 138                                N->getSrcValue(), N->getSrcValueOffset(),
 139                                N->getMemoryVT().getVectorElementType(),
 140                                N->isVolatile(), N->getAlignment());
 141
 142   // Legalized the chain result - switch anything that used the old chain to
 143   // use the new one.
 144   ReplaceValueWith(SDValue(N, 1), Result.getValue(1));
 145   return Result;
 146 }
 147
 148 SDValue DAGTypeLegalizer::ScalarizeVecRes_UnaryOp(SDNode *N) {
 149   // Get the dest type - it doesn't always match the input type, e.g. int_to_fp.
 150   MVT DestVT = N->getValueType(0).getVectorElementType();
 151   SDValue Op = GetScalarizedVector(N->getOperand(0));
 152   return DAG.getNode(N->getOpcode(), DestVT, Op);
 153 }
 154
 155 SDValue DAGTypeLegalizer::ScalarizeVecRes_UNDEF(SDNode *N) {
 156   return DAG.getNode(ISD::UNDEF, N->getValueType(0).getVectorElementType());
 157 }
 158
 159 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT(SDNode *N) {
 160   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 161   return DAG.getNode(ISD::SELECT, LHS.getValueType(), N->getOperand(0), LHS,
 162                      GetScalarizedVector(N->getOperand(2)));
 163 }
 164
 165 SDValue DAGTypeLegalizer::ScalarizeVecRes_VECTOR_SHUFFLE(SDNode *N) {
 166   // Figure out if the scalar is the LHS or RHS and return it.
 167   SDValue Arg = N->getOperand(2).getOperand(0);
 168   if (Arg.getOpcode() == ISD::UNDEF)
 169     return DAG.getNode(ISD::UNDEF, N->getValueType(0).getVectorElementType());
 170   unsigned Op = !cast<ConstantSDNode>(Arg)->isNullValue();
 171   return GetScalarizedVector(N->getOperand(Op));
 172 }
 173
 174 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSETCC(SDNode *N) {
 175   MVT NewVT = N->getValueType(0).getVectorElementType();
 176   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 177   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 178   LHS = DAG.getNode(ISD::SETCC, TLI.getSetCCResultType(LHS), LHS, RHS,
 179                     N->getOperand(2));
 180   return
 181     DAG.getNode(ISD::SELECT, NewVT, LHS,
 182                 DAG.getConstant(APInt::getAllOnesValue(NewVT.getSizeInBits()),
 183                                 NewVT),
 184                 DAG.getConstant(0ULL, NewVT));
 185 }
 186
 187
 188 //===----------------------------------------------------------------------===//
 189 //  Operand Vector Scalarization <1 x ty> -> ty.
 190 //===----------------------------------------------------------------------===//
 191
 192 bool DAGTypeLegalizer::ScalarizeVectorOperand(SDNode *N, unsigned OpNo) {
 193   DEBUG(cerr << "Scalarize node operand " << OpNo << ": "; N->dump(&DAG);
 194         cerr << "\n");
 195   SDValue Res = SDValue();
 196
 197   if (Res.getNode() == 0) {
 198     switch (N->getOpcode()) {
 199     default:
 200 #ifndef NDEBUG
 201       cerr << "ScalarizeVectorOperand Op #" << OpNo << ": ";
 202       N->dump(&DAG); cerr << "\n";
 203 #endif
 204       assert(0 && "Do not know how to scalarize this operator's operand!");
 205       abort();
 206
 207     case ISD::BIT_CONVERT:
 208       Res = ScalarizeVecOp_BIT_CONVERT(N); break;
 209
 210     case ISD::CONCAT_VECTORS:
 211       Res = ScalarizeVecOp_CONCAT_VECTORS(N); break;
 212
 213     case ISD::EXTRACT_VECTOR_ELT:
 214       Res = ScalarizeVecOp_EXTRACT_VECTOR_ELT(N); break;
 215
 216     case ISD::STORE:
 217       Res = ScalarizeVecOp_STORE(cast<StoreSDNode>(N), OpNo); break;
 218     }
 219   }
 220
 221   // If the result is null, the sub-method took care of registering results etc.
 222   if (!Res.getNode()) return false;
 223
 224   // If the result is N, the sub-method updated N in place.  Check to see if any
 225   // operands are new, and if so, mark them.
 226   if (Res.getNode() == N) {
 227     // Mark N as new and remark N and its operands.  This allows us to correctly
 228     // revisit N if it needs another step of promotion and allows us to visit
 229     // any new operands to N.
 230     ReanalyzeNode(N);
 231     return true;
 232   }
 233
 234   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 235          "Invalid operand expansion");
 236
 237   ReplaceValueWith(SDValue(N, 0), Res);
 238   return false;
 239 }
 240
 241 /// ScalarizeVecOp_BIT_CONVERT - If the value to convert is a vector that needs
 242 /// to be scalarized, it must be <1 x ty>.  Convert the element instead.
 243 SDValue DAGTypeLegalizer::ScalarizeVecOp_BIT_CONVERT(SDNode *N) {
 244   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 245   return DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0), Elt);
 246 }
 247
 248 /// ScalarizeVecOp_CONCAT_VECTORS - The vectors to concatenate have length one -
 249 /// use a BUILD_VECTOR instead.
 250 SDValue DAGTypeLegalizer::ScalarizeVecOp_CONCAT_VECTORS(SDNode *N) {
 251   SmallVector<SDValue, 8> Ops(N->getNumOperands());
 252   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i)
 253     Ops[i] = GetScalarizedVector(N->getOperand(i));
 254   return DAG.getNode(ISD::BUILD_VECTOR, N->getValueType(0),
 255                      &Ops[0], Ops.size());
 256 }
 257
 258 /// ScalarizeVecOp_EXTRACT_VECTOR_ELT - If the input is a vector that needs to
 259 /// be scalarized, it must be <1 x ty>, so just return the element, ignoring the
 260 /// index.
 261 SDValue DAGTypeLegalizer::ScalarizeVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
 262   return GetScalarizedVector(N->getOperand(0));
 263 }
 264
 265 /// ScalarizeVecOp_STORE - If the value to store is a vector that needs to be
 266 /// scalarized, it must be <1 x ty>.  Just store the element.
 267 SDValue DAGTypeLegalizer::ScalarizeVecOp_STORE(StoreSDNode *N, unsigned OpNo){
 268   assert(N->isUnindexed() && "Indexed store of one-element vector?");
 269   assert(OpNo == 1 && "Do not know how to scalarize this operand!");
 270
 271   if (N->isTruncatingStore())
 272     return DAG.getTruncStore(N->getChain(),
 273                              GetScalarizedVector(N->getOperand(1)),
 274                              N->getBasePtr(),
 275                              N->getSrcValue(), N->getSrcValueOffset(),
 276                              N->getMemoryVT().getVectorElementType(),
 277                              N->isVolatile(), N->getAlignment());
 278
 279   return DAG.getStore(N->getChain(), GetScalarizedVector(N->getOperand(1)),
 280                       N->getBasePtr(), N->getSrcValue(), N->getSrcValueOffset(),
 281                       N->isVolatile(), N->getAlignment());
 282 }
 283
 284
 285 //===----------------------------------------------------------------------===//
 286 //  Result Vector Splitting
 287 //===----------------------------------------------------------------------===//
 288
 289 /// SplitVectorResult - This method is called when the specified result of the
 290 /// specified node is found to need vector splitting.  At this point, the node
 291 /// may also have invalid operands or may have other results that need
 292 /// legalization, we just know that (at least) one result needs vector
 293 /// splitting.
 294 void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) {
 295   DEBUG(cerr << "Split node result: "; N->dump(&DAG); cerr << "\n");
 296   SDValue Lo, Hi;
 297
 298   switch (N->getOpcode()) {
 299   default:
 300 #ifndef NDEBUG
 301     cerr << "SplitVectorResult #" << ResNo << ": ";
 302     N->dump(&DAG); cerr << "\n";
 303 #endif
 304     assert(0 && "Do not know how to split the result of this operator!");
 305     abort();
 306
 307   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, Lo, Hi); break;
 308   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
 309   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
 310   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
 311
 312   case ISD::BIT_CONVERT:    SplitVecRes_BIT_CONVERT(N, Lo, Hi); break;
 313   case ISD::BUILD_VECTOR:   SplitVecRes_BUILD_VECTOR(N, Lo, Hi); break;
 314   case ISD::CONCAT_VECTORS: SplitVecRes_CONCAT_VECTORS(N, Lo, Hi); break;
 315   case ISD::FPOWI:          SplitVecRes_FPOWI(N, Lo, Hi); break;
 316   case ISD::INSERT_VECTOR_ELT: SplitVecRes_INSERT_VECTOR_ELT(N, Lo, Hi); break;
 317   case ISD::LOAD:           SplitVecRes_LOAD(cast<LoadSDNode>(N), Lo, Hi);break;
 318   case ISD::VECTOR_SHUFFLE: SplitVecRes_VECTOR_SHUFFLE(N, Lo, Hi); break;
 319   case ISD::VSETCC:         SplitVecRes_VSETCC(N, Lo, Hi); break;
 320
 321   case ISD::CTTZ:
 322   case ISD::CTLZ:
 323   case ISD::CTPOP:
 324   case ISD::FNEG:
 325   case ISD::FABS:
 326   case ISD::FSQRT:
 327   case ISD::FSIN:
 328   case ISD::FCOS:
 329   case ISD::FTRUNC:
 330   case ISD::FFLOOR:
 331   case ISD::FCEIL:
 332   case ISD::FRINT:
 333   case ISD::FNEARBYINT:
 334   case ISD::FP_TO_SINT:
 335   case ISD::FP_TO_UINT:
 336   case ISD::SINT_TO_FP:
 337   case ISD::TRUNCATE:
 338   case ISD::UINT_TO_FP: SplitVecRes_UnaryOp(N, Lo, Hi); break;
 339
 340   case ISD::ADD:
 341   case ISD::SUB:
 342   case ISD::MUL:
 343   case ISD::FADD:
 344   case ISD::FSUB:
 345   case ISD::FMUL:
 346   case ISD::SDIV:
 347   case ISD::UDIV:
 348   case ISD::FDIV:
 349   case ISD::FPOW:
 350   case ISD::AND:
 351   case ISD::OR:
 352   case ISD::XOR:
 353   case ISD::UREM:
 354   case ISD::SREM:
 355   case ISD::FREM: SplitVecRes_BinOp(N, Lo, Hi); break;
 356   }
 357
 358   // If Lo/Hi is null, the sub-method took care of registering results etc.
 359   if (Lo.getNode())
 360     SetSplitVector(SDValue(N, ResNo), Lo, Hi);
 361 }
 362
 363 void DAGTypeLegalizer::SplitVecRes_BinOp(SDNode *N, SDValue &Lo,
 364                                          SDValue &Hi) {
 365   SDValue LHSLo, LHSHi;
 366   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 367   SDValue RHSLo, RHSHi;
 368   GetSplitVector(N->getOperand(1), RHSLo, RHSHi);
 369
 370   Lo = DAG.getNode(N->getOpcode(), LHSLo.getValueType(), LHSLo, RHSLo);
 371   Hi = DAG.getNode(N->getOpcode(), LHSHi.getValueType(), LHSHi, RHSHi);
 372 }
 373
 374 void DAGTypeLegalizer::SplitVecRes_BIT_CONVERT(SDNode *N, SDValue &Lo,
 375                                                SDValue &Hi) {
 376   // We know the result is a vector.  The input may be either a vector or a
 377   // scalar value.
 378   MVT LoVT, HiVT;
 379   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 380
 381   SDValue InOp = N->getOperand(0);
 382   MVT InVT = InOp.getValueType();
 383
 384   // Handle some special cases efficiently.
 385   switch (getTypeAction(InVT)) {
 386   default:
 387     assert(false && "Unknown type action!");
 388   case Legal:
 389   case PromoteInteger:
 390   case SoftenFloat:
 391   case ScalarizeVector:
 392     break;
 393   case ExpandInteger:
 394   case ExpandFloat:
 395     // A scalar to vector conversion, where the scalar needs expansion.
 396     // If the vector is being split in two then we can just convert the
 397     // expanded pieces.
 398     if (LoVT == HiVT) {
 399       GetExpandedOp(InOp, Lo, Hi);
 400       if (TLI.isBigEndian())
 401         std::swap(Lo, Hi);
 402       Lo = DAG.getNode(ISD::BIT_CONVERT, LoVT, Lo);
 403       Hi = DAG.getNode(ISD::BIT_CONVERT, HiVT, Hi);
 404       return;
 405     }
 406     break;
 407   case SplitVector:
 408     // If the input is a vector that needs to be split, convert each split
 409     // piece of the input now.
 410     GetSplitVector(InOp, Lo, Hi);
 411     Lo = DAG.getNode(ISD::BIT_CONVERT, LoVT, Lo);
 412     Hi = DAG.getNode(ISD::BIT_CONVERT, HiVT, Hi);
 413     return;
 414   }
 415
 416   // In the general case, convert the input to an integer and split it by hand.
 417   MVT LoIntVT = MVT::getIntegerVT(LoVT.getSizeInBits());
 418   MVT HiIntVT = MVT::getIntegerVT(HiVT.getSizeInBits());
 419   if (TLI.isBigEndian())
 420     std::swap(LoIntVT, HiIntVT);
 421
 422   SplitInteger(BitConvertToInteger(InOp), LoIntVT, HiIntVT, Lo, Hi);
 423
 424   if (TLI.isBigEndian())
 425     std::swap(Lo, Hi);
 426   Lo = DAG.getNode(ISD::BIT_CONVERT, LoVT, Lo);
 427   Hi = DAG.getNode(ISD::BIT_CONVERT, HiVT, Hi);
 428 }
 429
 430 void DAGTypeLegalizer::SplitVecRes_BUILD_VECTOR(SDNode *N, SDValue &Lo,
 431                                                 SDValue &Hi) {
 432   MVT LoVT, HiVT;
 433   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 434   unsigned LoNumElts = LoVT.getVectorNumElements();
 435   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+LoNumElts);
 436   Lo = DAG.getNode(ISD::BUILD_VECTOR, LoVT, &LoOps[0], LoOps.size());
 437
 438   SmallVector<SDValue, 8> HiOps(N->op_begin()+LoNumElts, N->op_end());
 439   Hi = DAG.getNode(ISD::BUILD_VECTOR, HiVT, &HiOps[0], HiOps.size());
 440 }
 441
 442 void DAGTypeLegalizer::SplitVecRes_CONCAT_VECTORS(SDNode *N, SDValue &Lo,
 443                                                   SDValue &Hi) {
 444   assert(!(N->getNumOperands() & 1) && "Unsupported CONCAT_VECTORS");
 445   unsigned NumSubvectors = N->getNumOperands() / 2;
 446   if (NumSubvectors == 1) {
 447     Lo = N->getOperand(0);
 448     Hi = N->getOperand(1);
 449     return;
 450   }
 451
 452   MVT LoVT, HiVT;
 453   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 454
 455   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+NumSubvectors);
 456   Lo = DAG.getNode(ISD::CONCAT_VECTORS, LoVT, &LoOps[0], LoOps.size());
 457
 458   SmallVector<SDValue, 8> HiOps(N->op_begin()+NumSubvectors, N->op_end());
 459   Hi = DAG.getNode(ISD::CONCAT_VECTORS, HiVT, &HiOps[0], HiOps.size());
 460 }
 461
 462 void DAGTypeLegalizer::SplitVecRes_FPOWI(SDNode *N, SDValue &Lo,
 463                                          SDValue &Hi) {
 464   GetSplitVector(N->getOperand(0), Lo, Hi);
 465   Lo = DAG.getNode(ISD::FPOWI, Lo.getValueType(), Lo, N->getOperand(1));
 466   Hi = DAG.getNode(ISD::FPOWI, Hi.getValueType(), Hi, N->getOperand(1));
 467 }
 468
 469 void DAGTypeLegalizer::SplitVecRes_INSERT_VECTOR_ELT(SDNode *N, SDValue &Lo,
 470                                                      SDValue &Hi) {
 471   SDValue Vec = N->getOperand(0);
 472   SDValue Elt = N->getOperand(1);
 473   SDValue Idx = N->getOperand(2);
 474   GetSplitVector(Vec, Lo, Hi);
 475
 476   if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
 477     unsigned IdxVal = CIdx->getZExtValue();
 478     unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
 479     if (IdxVal < LoNumElts)
 480       Lo = DAG.getNode(ISD::INSERT_VECTOR_ELT, Lo.getValueType(), Lo, Elt, Idx);
 481     else
 482       Hi = DAG.getNode(ISD::INSERT_VECTOR_ELT, Hi.getValueType(), Hi, Elt,
 483                        DAG.getIntPtrConstant(IdxVal - LoNumElts));
 484     return;
 485   }
 486
 487   // Spill the vector to the stack.
 488   MVT VecVT = Vec.getValueType();
 489   MVT EltVT = VecVT.getVectorElementType();
 490   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
 491   SDValue Store = DAG.getStore(DAG.getEntryNode(), Vec, StackPtr, NULL, 0);
 492
 493   // Store the new element.  This may be larger than the vector element type,
 494   // so use a truncating store.
 495   SDValue EltPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
 496   Store = DAG.getTruncStore(Store, Elt, EltPtr, NULL, 0, EltVT);
 497
 498   // Reload the vector from the stack.
 499   SDValue Load = DAG.getLoad(VecVT, Store, StackPtr, NULL, 0);
 500
 501   // Split it.
 502   SplitVecRes_LOAD(cast<LoadSDNode>(Load.getNode()), Lo, Hi);
 503 }
 504
 505 void DAGTypeLegalizer::SplitVecRes_LOAD(LoadSDNode *LD, SDValue &Lo,
 506                                         SDValue &Hi) {
 507   assert(ISD::isUNINDEXEDLoad(LD) && "Indexed load during type legalization!");
 508   MVT LoVT, HiVT;
 509   GetSplitDestVTs(LD->getValueType(0), LoVT, HiVT);
 510
 511   ISD::LoadExtType ExtType = LD->getExtensionType();
 512   SDValue Ch = LD->getChain();
 513   SDValue Ptr = LD->getBasePtr();
 514   SDValue Offset = DAG.getNode(ISD::UNDEF, Ptr.getValueType());
 515   const Value *SV = LD->getSrcValue();
 516   int SVOffset = LD->getSrcValueOffset();
 517   MVT MemoryVT = LD->getMemoryVT();
 518   unsigned Alignment = LD->getAlignment();
 519   bool isVolatile = LD->isVolatile();
 520
 521   MVT LoMemVT, HiMemVT;
 522   GetSplitDestVTs(MemoryVT, LoMemVT, HiMemVT);
 523
 524   Lo = DAG.getLoad(ISD::UNINDEXED, ExtType, LoVT, Ch, Ptr, Offset,
 525                    SV, SVOffset, LoMemVT, isVolatile, Alignment);
 526
 527   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
 528   Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 529                     DAG.getIntPtrConstant(IncrementSize));
 530   SVOffset += IncrementSize;
 531   Alignment = MinAlign(Alignment, IncrementSize);
 532   Hi = DAG.getLoad(ISD::UNINDEXED, ExtType, HiVT, Ch, Ptr, Offset,
 533                    SV, SVOffset, HiMemVT, isVolatile, Alignment);
 534
 535   // Build a factor node to remember that this load is independent of the
 536   // other one.
 537   Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
 538                    Hi.getValue(1));
 539
 540   // Legalized the chain result - switch anything that used the old chain to
 541   // use the new one.
 542   ReplaceValueWith(SDValue(LD, 1), Ch);
 543 }
 544
 545 void DAGTypeLegalizer::SplitVecRes_UnaryOp(SDNode *N, SDValue &Lo,
 546                                            SDValue &Hi) {
 547   // Get the dest types - they may not match the input types, e.g. int_to_fp.
 548   MVT LoVT, HiVT;
 549   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 550
 551   // Split the input.
 552   MVT InVT = N->getOperand(0).getValueType();
 553   switch (getTypeAction(InVT)) {
 554   default: assert(0 && "Unexpected type action!");
 555   case Legal: {
 556     assert(LoVT == HiVT && "Legal non-power-of-two vector type?");
 557     MVT InNVT = MVT::getVectorVT(InVT.getVectorElementType(),
 558                                  LoVT.getVectorNumElements());
 559     Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, InNVT, N->getOperand(0),
 560                      DAG.getIntPtrConstant(0));
 561     Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, InNVT, N->getOperand(0),
 562                      DAG.getIntPtrConstant(InNVT.getVectorNumElements()));
 563     break;
 564   }
 565   case SplitVector:
 566     GetSplitVector(N->getOperand(0), Lo, Hi);
 567     break;
 568   }
 569
 570   Lo = DAG.getNode(N->getOpcode(), LoVT, Lo);
 571   Hi = DAG.getNode(N->getOpcode(), HiVT, Hi);
 572 }
 573
 574 void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo,
 575                                                   SDValue &Hi) {
 576   // Build the low part.
 577   SDValue Mask = N->getOperand(2);
 578   SmallVector<SDValue, 16> Ops;
 579   MVT LoVT, HiVT;
 580   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 581   MVT EltVT = LoVT.getVectorElementType();
 582   unsigned LoNumElts = LoVT.getVectorNumElements();
 583   unsigned NumElements = Mask.getNumOperands();
 584
 585   // Insert all of the elements from the input that are needed.  We use
 586   // buildvector of extractelement here because the input vectors will have
 587   // to be legalized, so this makes the code simpler.
 588   for (unsigned i = 0; i != LoNumElts; ++i) {
 589     SDValue Arg = Mask.getOperand(i);
 590     if (Arg.getOpcode() == ISD::UNDEF) {
 591       Ops.push_back(DAG.getNode(ISD::UNDEF, EltVT));
 592     } else {
 593       unsigned Idx = cast<ConstantSDNode>(Mask.getOperand(i))->getZExtValue();
 594       SDValue InVec = N->getOperand(0);
 595       if (Idx >= NumElements) {
 596         InVec = N->getOperand(1);
 597         Idx -= NumElements;
 598       }
 599       Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, InVec,
 600                                 DAG.getIntPtrConstant(Idx)));
 601     }
 602   }
 603   Lo = DAG.getNode(ISD::BUILD_VECTOR, LoVT, &Ops[0], Ops.size());
 604   Ops.clear();
 605
 606   for (unsigned i = LoNumElts; i != NumElements; ++i) {
 607     unsigned Idx = cast<ConstantSDNode>(Mask.getOperand(i))->getZExtValue();
 608     SDValue InVec = N->getOperand(0);
 609     if (Idx >= NumElements) {
 610       InVec = N->getOperand(1);
 611       Idx -= NumElements;
 612     }
 613     Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, InVec,
 614                               DAG.getIntPtrConstant(Idx)));
 615   }
 616   Hi = DAG.getNode(ISD::BUILD_VECTOR, HiVT, &Ops[0], Ops.size());
 617 }
 618
 619 void DAGTypeLegalizer::SplitVecRes_VSETCC(SDNode *N, SDValue &Lo,
 620                                           SDValue &Hi) {
 621   MVT LoVT, HiVT;
 622   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 623
 624   SDValue LL, LH, RL, RH;
 625   GetSplitVector(N->getOperand(0), LL, LH);
 626   GetSplitVector(N->getOperand(1), RL, RH);
 627
 628   Lo = DAG.getNode(ISD::VSETCC, LoVT, LL, RL, N->getOperand(2));
 629   Hi = DAG.getNode(ISD::VSETCC, HiVT, LH, RH, N->getOperand(2));
 630 }
 631
 632
 633 //===----------------------------------------------------------------------===//
 634 //  Operand Vector Splitting
 635 //===----------------------------------------------------------------------===//
 636
 637 /// SplitVectorOperand - This method is called when the specified operand of the
 638 /// specified node is found to need vector splitting.  At this point, all of the
 639 /// result types of the node are known to be legal, but other operands of the
 640 /// node may need legalization as well as the specified one.
 641 bool DAGTypeLegalizer::SplitVectorOperand(SDNode *N, unsigned OpNo) {
 642   DEBUG(cerr << "Split node operand: "; N->dump(&DAG); cerr << "\n");
 643   SDValue Res = SDValue();
 644
 645   if (Res.getNode() == 0) {
 646     switch (N->getOpcode()) {
 647     default:
 648 #ifndef NDEBUG
 649       cerr << "SplitVectorOperand Op #" << OpNo << ": ";
 650       N->dump(&DAG); cerr << "\n";
 651 #endif
 652       assert(0 && "Do not know how to split this operator's operand!");
 653       abort();
 654
 655     case ISD::BIT_CONVERT:       Res = SplitVecOp_BIT_CONVERT(N); break;
 656     case ISD::EXTRACT_SUBVECTOR: Res = SplitVecOp_EXTRACT_SUBVECTOR(N); break;
 657     case ISD::EXTRACT_VECTOR_ELT:Res = SplitVecOp_EXTRACT_VECTOR_ELT(N); break;
 658     case ISD::STORE:             Res = SplitVecOp_STORE(cast<StoreSDNode>(N),
 659                                                         OpNo); break;
 660     case ISD::VECTOR_SHUFFLE:    Res = SplitVecOp_VECTOR_SHUFFLE(N, OpNo);break;
 661
 662     case ISD::CTTZ:
 663     case ISD::CTLZ:
 664     case ISD::CTPOP:
 665     case ISD::FP_TO_SINT:
 666     case ISD::FP_TO_UINT:
 667     case ISD::SINT_TO_FP:
 668     case ISD::TRUNCATE:
 669     case ISD::UINT_TO_FP: Res = SplitVecOp_UnaryOp(N); break;
 670     }
 671   }
 672
 673   // If the result is null, the sub-method took care of registering results etc.
 674   if (!Res.getNode()) return false;
 675
 676   // If the result is N, the sub-method updated N in place.  Check to see if any
 677   // operands are new, and if so, mark them.
 678   if (Res.getNode() == N) {
 679     // Mark N as new and remark N and its operands.  This allows us to correctly
 680     // revisit N if it needs another step of promotion and allows us to visit
 681     // any new operands to N.
 682     ReanalyzeNode(N);
 683     return true;
 684   }
 685
 686   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 687          "Invalid operand expansion");
 688
 689   ReplaceValueWith(SDValue(N, 0), Res);
 690   return false;
 691 }
 692
 693 SDValue DAGTypeLegalizer::SplitVecOp_UnaryOp(SDNode *N) {
 694   // The result has a legal vector type, but the input needs splitting.
 695   MVT ResVT = N->getValueType(0);
 696   SDValue Lo, Hi;
 697   GetSplitVector(N->getOperand(0), Lo, Hi);
 698   assert(Lo.getValueType() == Hi.getValueType() &&
 699          "Returns legal non-power-of-two vector type?");
 700   MVT InVT = Lo.getValueType();
 701
 702   MVT OutVT = MVT::getVectorVT(ResVT.getVectorElementType(),
 703                                InVT.getVectorNumElements());
 704
 705   Lo = DAG.getNode(N->getOpcode(), OutVT, Lo);
 706   Hi = DAG.getNode(N->getOpcode(), OutVT, Hi);
 707
 708   return DAG.getNode(ISD::CONCAT_VECTORS, ResVT, Lo, Hi);
 709 }
 710
 711 SDValue DAGTypeLegalizer::SplitVecOp_BIT_CONVERT(SDNode *N) {
 712   // For example, i64 = BIT_CONVERT v4i16 on alpha.  Typically the vector will
 713   // end up being split all the way down to individual components.  Convert the
 714   // split pieces into integers and reassemble.
 715   SDValue Lo, Hi;
 716   GetSplitVector(N->getOperand(0), Lo, Hi);
 717   Lo = BitConvertToInteger(Lo);
 718   Hi = BitConvertToInteger(Hi);
 719
 720   if (TLI.isBigEndian())
 721     std::swap(Lo, Hi);
 722
 723   return DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0),
 724                      JoinIntegers(Lo, Hi));
 725 }
 726
 727 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
 728   // We know that the extracted result type is legal.  For now, assume the index
 729   // is a constant.
 730   MVT SubVT = N->getValueType(0);
 731   SDValue Idx = N->getOperand(1);
 732   SDValue Lo, Hi;
 733   GetSplitVector(N->getOperand(0), Lo, Hi);
 734
 735   uint64_t LoElts = Lo.getValueType().getVectorNumElements();
 736   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
 737
 738   if (IdxVal < LoElts) {
 739     assert(IdxVal + SubVT.getVectorNumElements() <= LoElts &&
 740            "Extracted subvector crosses vector split!");
 741     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SubVT, Lo, Idx);
 742   } else {
 743     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SubVT, Hi,
 744                        DAG.getConstant(IdxVal - LoElts, Idx.getValueType()));
 745   }
 746 }
 747
 748 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
 749   SDValue Vec = N->getOperand(0);
 750   SDValue Idx = N->getOperand(1);
 751   MVT VecVT = Vec.getValueType();
 752
 753   if (isa<ConstantSDNode>(Idx)) {
 754     uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
 755     assert(IdxVal < VecVT.getVectorNumElements() && "Invalid vector index!");
 756
 757     SDValue Lo, Hi;
 758     GetSplitVector(Vec, Lo, Hi);
 759
 760     uint64_t LoElts = Lo.getValueType().getVectorNumElements();
 761
 762     if (IdxVal < LoElts)
 763       return DAG.UpdateNodeOperands(SDValue(N, 0), Lo, Idx);
 764     else
 765       return DAG.UpdateNodeOperands(SDValue(N, 0), Hi,
 766                                     DAG.getConstant(IdxVal - LoElts,
 767                                                     Idx.getValueType()));
 768   }
 769
 770   // Store the vector to the stack.
 771   MVT EltVT = VecVT.getVectorElementType();
 772   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
 773   SDValue Store = DAG.getStore(DAG.getEntryNode(), Vec, StackPtr, NULL, 0);
 774
 775   // Load back the required element.
 776   StackPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
 777   return DAG.getLoad(EltVT, Store, StackPtr, NULL, 0);
 778 }
 779
 780 SDValue DAGTypeLegalizer::SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo) {
 781   assert(N->isUnindexed() && "Indexed store of vector?");
 782   assert(OpNo == 1 && "Can only split the stored value");
 783
 784   bool isTruncating = N->isTruncatingStore();
 785   SDValue Ch  = N->getChain();
 786   SDValue Ptr = N->getBasePtr();
 787   int SVOffset = N->getSrcValueOffset();
 788   MVT MemoryVT = N->getMemoryVT();
 789   unsigned Alignment = N->getAlignment();
 790   bool isVol = N->isVolatile();
 791   SDValue Lo, Hi;
 792   GetSplitVector(N->getOperand(1), Lo, Hi);
 793
 794   MVT LoMemVT, HiMemVT;
 795   GetSplitDestVTs(MemoryVT, LoMemVT, HiMemVT);
 796
 797   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
 798
 799   if (isTruncating)
 800     Lo = DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
 801                            LoMemVT, isVol, Alignment);
 802   else
 803     Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
 804                       isVol, Alignment);
 805
 806   // Increment the pointer to the other half.
 807   Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 808                     DAG.getIntPtrConstant(IncrementSize));
 809
 810   if (isTruncating)
 811     Hi = DAG.getTruncStore(Ch, Hi, Ptr,
 812                            N->getSrcValue(), SVOffset+IncrementSize,
 813                            HiMemVT,
 814                            isVol, MinAlign(Alignment, IncrementSize));
 815   else
 816     Hi = DAG.getStore(Ch, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
 817                       isVol, MinAlign(Alignment, IncrementSize));
 818
 819   return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 820 }
 821
 822 SDValue DAGTypeLegalizer::SplitVecOp_VECTOR_SHUFFLE(SDNode *N, unsigned OpNo) {
 823   assert(OpNo == 2 && "Shuffle source type differs from result type?");
 824   SDValue Mask = N->getOperand(2);
 825   unsigned MaskLength = Mask.getValueType().getVectorNumElements();
 826   unsigned LargestMaskEntryPlusOne = 2 * MaskLength;
 827   unsigned MinimumBitWidth = Log2_32_Ceil(LargestMaskEntryPlusOne);
 828
 829   // Look for a legal vector type to place the mask values in.
 830   // Note that there may not be *any* legal vector-of-integer
 831   // type for which the element type is legal!
 832   for (MVT::SimpleValueType EltVT = MVT::FIRST_INTEGER_VALUETYPE;
 833        EltVT <= MVT::LAST_INTEGER_VALUETYPE;
 834        // Integer values types are consecutively numbered.  Exploit this.
 835        EltVT = MVT::SimpleValueType(EltVT + 1)) {
 836
 837     // Is the element type big enough to hold the values?
 838     if (MVT(EltVT).getSizeInBits() < MinimumBitWidth)
 839       // Nope.
 840       continue;
 841
 842     // Is the vector type legal?
 843     MVT VecVT = MVT::getVectorVT(EltVT, MaskLength);
 844     if (!isTypeLegal(VecVT))
 845       // Nope.
 846       continue;
 847
 848     // If the element type is not legal, find a larger legal type to use for
 849     // the BUILD_VECTOR operands.  This is an ugly hack, but seems to work!
 850     // FIXME: The real solution is to change VECTOR_SHUFFLE into a variadic
 851     // node where the shuffle mask is a list of integer operands, #2 .. #2+n.
 852     for (MVT::SimpleValueType OpVT = EltVT; OpVT <= MVT::LAST_INTEGER_VALUETYPE;
 853          // Integer values types are consecutively numbered.  Exploit this.
 854          OpVT = MVT::SimpleValueType(OpVT + 1)) {
 855       if (!isTypeLegal(OpVT))
 856         continue;
 857
 858       // Success!  Rebuild the vector using the legal types.
 859       SmallVector<SDValue, 16> Ops(MaskLength);
 860       for (unsigned i = 0; i < MaskLength; ++i) {
 861         SDValue Arg = Mask.getOperand(i);
 862         if (Arg.getOpcode() == ISD::UNDEF) {
 863           Ops[i] = DAG.getNode(ISD::UNDEF, OpVT);
 864         } else {
 865           uint64_t Idx = cast<ConstantSDNode>(Arg)->getZExtValue();
 866           Ops[i] = DAG.getConstant(Idx, OpVT);
 867         }
 868       }
 869       return DAG.UpdateNodeOperands(SDValue(N,0),
 870                                     N->getOperand(0), N->getOperand(1),
 871                                     DAG.getNode(ISD::BUILD_VECTOR,
 872                                                 VecVT, &Ops[0], Ops.size()));
 873     }
 874
 875     // Continuing is pointless - failure is certain.
 876     break;
 877   }
 878   assert(false && "Failed to find an appropriate mask type!");
 879   return SDValue(N, 0);
 880 }