lib/CodeGen/SelectionDAG/LegalizeTypesSplit.cpp

   1 //===-- LegalizeTypesSplit.cpp - Vector Splitting for LegalizeTypes -------===//
   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 implements vector splitting support for LegalizeTypes.  Vector
  11 // splitting is the act of changing a computation in an invalid vector type to
  12 // be a computation in multiple vectors of a smaller type.  For example,
  13 // implementing <128 x f32> operations in terms of two <64 x f32> operations.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "LegalizeTypes.h"
  18 using namespace llvm;
  19
  20 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a vector
  21 /// type that needs to be split.  This handles non-power of two vectors.
  22 static void GetSplitDestVTs(MVT InVT, MVT &Lo, MVT &Hi) {
  23   MVT NewEltVT = InVT.getVectorElementType();
  24   unsigned NumElements = InVT.getVectorNumElements();
  25   if ((NumElements & (NumElements-1)) == 0) {  // Simple power of two vector.
  26     NumElements >>= 1;
  27     Lo = Hi =  MVT::getVectorVT(NewEltVT, NumElements);
  28   } else {                                     // Non-power-of-two vectors.
  29     unsigned NewNumElts_Lo = 1 << Log2_32(NumElements);
  30     unsigned NewNumElts_Hi = NumElements - NewNumElts_Lo;
  31     Lo = MVT::getVectorVT(NewEltVT, NewNumElts_Lo);
  32     Hi = MVT::getVectorVT(NewEltVT, NewNumElts_Hi);
  33   }
  34 }
  35
  36
  37 //===----------------------------------------------------------------------===//
  38 //  Result Vector Splitting
  39 //===----------------------------------------------------------------------===//
  40
  41 /// SplitResult - This method is called when the specified result of the
  42 /// specified node is found to need vector splitting.  At this point, the node
  43 /// may also have invalid operands or may have other results that need
  44 /// legalization, we just know that (at least) one result needs vector
  45 /// splitting.
  46 void DAGTypeLegalizer::SplitResult(SDNode *N, unsigned ResNo) {
  47   DEBUG(cerr << "Split node result: "; N->dump(&DAG); cerr << "\n");
  48   SDOperand Lo, Hi;
  49
  50 #if 0
  51   // See if the target wants to custom expand this node.
  52   if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
  53       TargetLowering::Custom) {
  54     // If the target wants to, allow it to lower this itself.
  55     if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) {
  56       // Everything that once used N now uses P.  We are guaranteed that the
  57       // result value types of N and the result value types of P match.
  58       ReplaceNodeWith(N, P);
  59       return;
  60     }
  61   }
  62 #endif
  63
  64   switch (N->getOpcode()) {
  65   default:
  66 #ifndef NDEBUG
  67     cerr << "SplitResult #" << ResNo << ": ";
  68     N->dump(&DAG); cerr << "\n";
  69 #endif
  70     assert(0 && "Do not know how to split the result of this operator!");
  71     abort();
  72
  73   case ISD::UNDEF:            SplitRes_UNDEF(N, Lo, Hi); break;
  74   case ISD::LOAD:             SplitRes_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
  75   case ISD::BUILD_PAIR:       SplitRes_BUILD_PAIR(N, Lo, Hi); break;
  76   case ISD::INSERT_VECTOR_ELT:SplitRes_INSERT_VECTOR_ELT(N, Lo, Hi); break;
  77   case ISD::VECTOR_SHUFFLE:   SplitRes_VECTOR_SHUFFLE(N, Lo, Hi); break;
  78   case ISD::BUILD_VECTOR:     SplitRes_BUILD_VECTOR(N, Lo, Hi); break;
  79   case ISD::CONCAT_VECTORS:   SplitRes_CONCAT_VECTORS(N, Lo, Hi); break;
  80   case ISD::BIT_CONVERT:      SplitRes_BIT_CONVERT(N, Lo, Hi); break;
  81   case ISD::CTTZ:
  82   case ISD::CTLZ:
  83   case ISD::CTPOP:
  84   case ISD::FNEG:
  85   case ISD::FABS:
  86   case ISD::FSQRT:
  87   case ISD::FSIN:
  88   case ISD::FCOS:
  89   case ISD::FP_TO_SINT:
  90   case ISD::FP_TO_UINT:
  91   case ISD::SINT_TO_FP:
  92   case ISD::UINT_TO_FP:       SplitRes_UnOp(N, Lo, Hi); break;
  93   case ISD::ADD:
  94   case ISD::SUB:
  95   case ISD::MUL:
  96   case ISD::FADD:
  97   case ISD::FSUB:
  98   case ISD::FMUL:
  99   case ISD::SDIV:
 100   case ISD::UDIV:
 101   case ISD::FDIV:
 102   case ISD::FPOW:
 103   case ISD::AND:
 104   case ISD::OR:
 105   case ISD::XOR:
 106   case ISD::UREM:
 107   case ISD::SREM:
 108   case ISD::FREM:             SplitRes_BinOp(N, Lo, Hi); break;
 109   case ISD::FPOWI:            SplitRes_FPOWI(N, Lo, Hi); break;
 110   case ISD::SELECT:           SplitRes_SELECT(N, Lo, Hi); break;
 111   }
 112
 113   // If Lo/Hi is null, the sub-method took care of registering results etc.
 114   if (Lo.Val)
 115     SetSplitOp(SDOperand(N, ResNo), Lo, Hi);
 116 }
 117
 118 void DAGTypeLegalizer::SplitRes_UNDEF(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 119   MVT LoVT, HiVT;
 120   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 121
 122   Lo = DAG.getNode(ISD::UNDEF, LoVT);
 123   Hi = DAG.getNode(ISD::UNDEF, HiVT);
 124 }
 125
 126 void DAGTypeLegalizer::SplitRes_LOAD(LoadSDNode *LD,
 127                                      SDOperand &Lo, SDOperand &Hi) {
 128   // FIXME: Add support for indexed loads.
 129   MVT LoVT, HiVT;
 130   GetSplitDestVTs(LD->getValueType(0), LoVT, HiVT);
 131
 132   SDOperand Ch = LD->getChain();
 133   SDOperand Ptr = LD->getBasePtr();
 134   const Value *SV = LD->getSrcValue();
 135   int SVOffset = LD->getSrcValueOffset();
 136   unsigned Alignment = LD->getAlignment();
 137   bool isVolatile = LD->isVolatile();
 138
 139   Lo = DAG.getLoad(LoVT, Ch, Ptr, SV, SVOffset, isVolatile, Alignment);
 140   unsigned IncrementSize = LoVT.getSizeInBits()/8;
 141   Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 142                     DAG.getIntPtrConstant(IncrementSize));
 143   SVOffset += IncrementSize;
 144   Alignment = MinAlign(Alignment, IncrementSize);
 145   Hi = DAG.getLoad(HiVT, Ch, Ptr, SV, SVOffset, isVolatile, Alignment);
 146
 147   // Build a factor node to remember that this load is independent of the
 148   // other one.
 149   SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
 150                              Hi.getValue(1));
 151
 152   // Legalized the chain result - switch anything that used the old chain to
 153   // use the new one.
 154   ReplaceValueWith(SDOperand(LD, 1), TF);
 155 }
 156
 157 void DAGTypeLegalizer::SplitRes_BUILD_PAIR(SDNode *N, SDOperand &Lo,
 158                                            SDOperand &Hi) {
 159   Lo = N->getOperand(0);
 160   Hi = N->getOperand(1);
 161 }
 162
 163 void DAGTypeLegalizer::SplitRes_INSERT_VECTOR_ELT(SDNode *N, SDOperand &Lo,
 164                                                   SDOperand &Hi) {
 165   SDOperand Vec = N->getOperand(0);
 166   SDOperand Elt = N->getOperand(1);
 167   SDOperand Idx = N->getOperand(2);
 168   GetSplitOp(Vec, Lo, Hi);
 169
 170   if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
 171     unsigned IdxVal = CIdx->getValue();
 172     unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
 173     if (IdxVal < LoNumElts)
 174       Lo = DAG.getNode(ISD::INSERT_VECTOR_ELT, Lo.getValueType(), Lo, Elt, Idx);
 175     else
 176       Hi = DAG.getNode(ISD::INSERT_VECTOR_ELT, Hi.getValueType(), Hi, Elt,
 177                        DAG.getIntPtrConstant(IdxVal - LoNumElts));
 178     return;
 179   }
 180
 181   // Spill the vector to the stack.
 182   MVT VecVT = Vec.getValueType();
 183   SDOperand StackPtr = DAG.CreateStackTemporary(VecVT);
 184   SDOperand Store = DAG.getStore(DAG.getEntryNode(), Vec, StackPtr, NULL, 0);
 185
 186   // Store the new element.
 187   SDOperand EltPtr = GetVectorElementPointer(StackPtr,
 188                                              VecVT.getVectorElementType(), Idx);
 189   Store = DAG.getStore(Store, Elt, EltPtr, NULL, 0);
 190
 191   // Reload the vector from the stack.
 192   SDOperand Load = DAG.getLoad(VecVT, Store, StackPtr, NULL, 0);
 193
 194   // Split it.
 195   SplitRes_LOAD(cast<LoadSDNode>(Load.Val), Lo, Hi);
 196 }
 197
 198 void DAGTypeLegalizer::SplitRes_VECTOR_SHUFFLE(SDNode *N,
 199                                                SDOperand &Lo, SDOperand &Hi) {
 200   // Build the low part.
 201   SDOperand Mask = N->getOperand(2);
 202   SmallVector<SDOperand, 16> Ops;
 203   MVT LoVT, HiVT;
 204   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 205   MVT EltVT = LoVT.getVectorElementType();
 206   unsigned LoNumElts = LoVT.getVectorNumElements();
 207   unsigned NumElements = Mask.getNumOperands();
 208
 209   // Insert all of the elements from the input that are needed.  We use
 210   // buildvector of extractelement here because the input vectors will have
 211   // to be legalized, so this makes the code simpler.
 212   for (unsigned i = 0; i != LoNumElts; ++i) {
 213     unsigned Idx = cast<ConstantSDNode>(Mask.getOperand(i))->getValue();
 214     SDOperand InVec = N->getOperand(0);
 215     if (Idx >= NumElements) {
 216       InVec = N->getOperand(1);
 217       Idx -= NumElements;
 218     }
 219     Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, InVec,
 220                               DAG.getIntPtrConstant(Idx)));
 221   }
 222   Lo = DAG.getNode(ISD::BUILD_VECTOR, LoVT, &Ops[0], Ops.size());
 223   Ops.clear();
 224
 225   for (unsigned i = LoNumElts; i != NumElements; ++i) {
 226     unsigned Idx = cast<ConstantSDNode>(Mask.getOperand(i))->getValue();
 227     SDOperand InVec = N->getOperand(0);
 228     if (Idx >= NumElements) {
 229       InVec = N->getOperand(1);
 230       Idx -= NumElements;
 231     }
 232     Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, InVec,
 233                               DAG.getIntPtrConstant(Idx)));
 234   }
 235   Hi = DAG.getNode(ISD::BUILD_VECTOR, HiVT, &Ops[0], Ops.size());
 236 }
 237
 238 void DAGTypeLegalizer::SplitRes_BUILD_VECTOR(SDNode *N, SDOperand &Lo,
 239                                              SDOperand &Hi) {
 240   MVT LoVT, HiVT;
 241   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 242   unsigned LoNumElts = LoVT.getVectorNumElements();
 243   SmallVector<SDOperand, 8> LoOps(N->op_begin(), N->op_begin()+LoNumElts);
 244   Lo = DAG.getNode(ISD::BUILD_VECTOR, LoVT, &LoOps[0], LoOps.size());
 245
 246   SmallVector<SDOperand, 8> HiOps(N->op_begin()+LoNumElts, N->op_end());
 247   Hi = DAG.getNode(ISD::BUILD_VECTOR, HiVT, &HiOps[0], HiOps.size());
 248 }
 249
 250 void DAGTypeLegalizer::SplitRes_CONCAT_VECTORS(SDNode *N,
 251                                                SDOperand &Lo, SDOperand &Hi) {
 252   // FIXME: Handle non-power-of-two vectors?
 253   unsigned NumSubvectors = N->getNumOperands() / 2;
 254   if (NumSubvectors == 1) {
 255     Lo = N->getOperand(0);
 256     Hi = N->getOperand(1);
 257     return;
 258   }
 259
 260   MVT LoVT, HiVT;
 261   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 262
 263   SmallVector<SDOperand, 8> LoOps(N->op_begin(), N->op_begin()+NumSubvectors);
 264   Lo = DAG.getNode(ISD::CONCAT_VECTORS, LoVT, &LoOps[0], LoOps.size());
 265
 266   SmallVector<SDOperand, 8> HiOps(N->op_begin()+NumSubvectors, N->op_end());
 267   Hi = DAG.getNode(ISD::CONCAT_VECTORS, HiVT, &HiOps[0], HiOps.size());
 268 }
 269
 270 void DAGTypeLegalizer::SplitRes_BIT_CONVERT(SDNode *N,
 271                                             SDOperand &Lo, SDOperand &Hi) {
 272   // We know the result is a vector.  The input may be either a vector or a
 273   // scalar value.
 274   MVT LoVT, HiVT;
 275   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 276
 277   SDOperand InOp = N->getOperand(0);
 278   MVT InVT = InOp.getValueType();
 279
 280   // Handle some special cases efficiently.
 281   switch (getTypeAction(InVT)) {
 282   default:
 283     assert(false && "Unknown type action!");
 284   case Legal:
 285   case FloatToInt:
 286   case Promote:
 287   case Scalarize:
 288     break;
 289   case Expand:
 290     // A scalar to vector conversion, where the scalar needs expansion.
 291     // If the vector is being split in two then we can just convert the
 292     // expanded pieces.
 293     if (LoVT == HiVT) {
 294       GetExpandedOp(InOp, Lo, Hi);
 295       if (TLI.isBigEndian())
 296         std::swap(Lo, Hi);
 297       Lo = DAG.getNode(ISD::BIT_CONVERT, LoVT, Lo);
 298       Hi = DAG.getNode(ISD::BIT_CONVERT, HiVT, Hi);
 299       return;
 300     }
 301     break;
 302   case Split:
 303     // If the input is a vector that needs to be split, convert each split
 304     // piece of the input now.
 305     GetSplitOp(InOp, Lo, Hi);
 306     Lo = DAG.getNode(ISD::BIT_CONVERT, LoVT, Lo);
 307     Hi = DAG.getNode(ISD::BIT_CONVERT, HiVT, Hi);
 308     return;
 309   }
 310
 311   // In the general case, convert the input to an integer and split it by hand.
 312   MVT LoIntVT = MVT::getIntegerVT(LoVT.getSizeInBits());
 313   MVT HiIntVT = MVT::getIntegerVT(HiVT.getSizeInBits());
 314   if (TLI.isBigEndian())
 315     std::swap(LoIntVT, HiIntVT);
 316
 317   SplitInteger(BitConvertToInteger(InOp), LoIntVT, HiIntVT, Lo, Hi);
 318
 319   if (TLI.isBigEndian())
 320     std::swap(Lo, Hi);
 321   Lo = DAG.getNode(ISD::BIT_CONVERT, LoVT, Lo);
 322   Hi = DAG.getNode(ISD::BIT_CONVERT, HiVT, Hi);
 323 }
 324
 325 void DAGTypeLegalizer::SplitRes_BinOp(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 326   SDOperand LHSLo, LHSHi;
 327   GetSplitOp(N->getOperand(0), LHSLo, LHSHi);
 328   SDOperand RHSLo, RHSHi;
 329   GetSplitOp(N->getOperand(1), RHSLo, RHSHi);
 330
 331   Lo = DAG.getNode(N->getOpcode(), LHSLo.getValueType(), LHSLo, RHSLo);
 332   Hi = DAG.getNode(N->getOpcode(), LHSHi.getValueType(), LHSHi, RHSHi);
 333 }
 334
 335 void DAGTypeLegalizer::SplitRes_UnOp(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 336   // Get the dest types.  This doesn't always match input types, e.g. int_to_fp.
 337   MVT LoVT, HiVT;
 338   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 339
 340   GetSplitOp(N->getOperand(0), Lo, Hi);
 341   Lo = DAG.getNode(N->getOpcode(), LoVT, Lo);
 342   Hi = DAG.getNode(N->getOpcode(), HiVT, Hi);
 343 }
 344
 345 void DAGTypeLegalizer::SplitRes_FPOWI(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
 346   GetSplitOp(N->getOperand(0), Lo, Hi);
 347   Lo = DAG.getNode(ISD::FPOWI, Lo.getValueType(), Lo, N->getOperand(1));
 348   Hi = DAG.getNode(ISD::FPOWI, Lo.getValueType(), Hi, N->getOperand(1));
 349 }
 350
 351
 352 void DAGTypeLegalizer::SplitRes_SELECT(SDNode *N, SDOperand &Lo, SDOperand &Hi){
 353   SDOperand LL, LH, RL, RH;
 354   GetSplitOp(N->getOperand(1), LL, LH);
 355   GetSplitOp(N->getOperand(2), RL, RH);
 356
 357   SDOperand Cond = N->getOperand(0);
 358   Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), Cond, LL, RL);
 359   Hi = DAG.getNode(ISD::SELECT, LH.getValueType(), Cond, LH, RH);
 360 }
 361
 362
 363 //===----------------------------------------------------------------------===//
 364 //  Operand Vector Splitting
 365 //===----------------------------------------------------------------------===//
 366
 367 /// SplitOperand - This method is called when the specified operand of the
 368 /// specified node is found to need vector splitting.  At this point, all of the
 369 /// result types of the node are known to be legal, but other operands of the
 370 /// node may need legalization as well as the specified one.
 371 bool DAGTypeLegalizer::SplitOperand(SDNode *N, unsigned OpNo) {
 372   DEBUG(cerr << "Split node operand: "; N->dump(&DAG); cerr << "\n");
 373   SDOperand Res(0, 0);
 374
 375 #if 0
 376   if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
 377       TargetLowering::Custom)
 378     Res = TLI.LowerOperation(SDOperand(N, 0), DAG);
 379 #endif
 380
 381   if (Res.Val == 0) {
 382     switch (N->getOpcode()) {
 383     default:
 384 #ifndef NDEBUG
 385       cerr << "SplitOperand Op #" << OpNo << ": ";
 386       N->dump(&DAG); cerr << "\n";
 387 #endif
 388       assert(0 && "Do not know how to split this operator's operand!");
 389       abort();
 390     case ISD::STORE: Res = SplitOp_STORE(cast<StoreSDNode>(N), OpNo); break;
 391     case ISD::RET:   Res = SplitOp_RET(N, OpNo); break;
 392
 393     case ISD::BIT_CONVERT: Res = SplitOp_BIT_CONVERT(N); break;
 394
 395     case ISD::EXTRACT_VECTOR_ELT: Res = SplitOp_EXTRACT_VECTOR_ELT(N); break;
 396     case ISD::EXTRACT_SUBVECTOR:  Res = SplitOp_EXTRACT_SUBVECTOR(N); break;
 397     case ISD::VECTOR_SHUFFLE:     Res = SplitOp_VECTOR_SHUFFLE(N, OpNo); break;
 398     }
 399   }
 400
 401   // If the result is null, the sub-method took care of registering results etc.
 402   if (!Res.Val) return false;
 403
 404   // If the result is N, the sub-method updated N in place.  Check to see if any
 405   // operands are new, and if so, mark them.
 406   if (Res.Val == N) {
 407     // Mark N as new and remark N and its operands.  This allows us to correctly
 408     // revisit N if it needs another step of promotion and allows us to visit
 409     // any new operands to N.
 410     ReanalyzeNode(N);
 411     return true;
 412   }
 413
 414   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 415          "Invalid operand expansion");
 416
 417   ReplaceValueWith(SDOperand(N, 0), Res);
 418   return false;
 419 }
 420
 421 SDOperand DAGTypeLegalizer::SplitOp_STORE(StoreSDNode *N, unsigned OpNo) {
 422   // FIXME: Add support for indexed stores.
 423   assert(OpNo == 1 && "Can only split the stored value");
 424
 425   SDOperand Ch  = N->getChain();
 426   SDOperand Ptr = N->getBasePtr();
 427   int SVOffset = N->getSrcValueOffset();
 428   unsigned Alignment = N->getAlignment();
 429   bool isVol = N->isVolatile();
 430   SDOperand Lo, Hi;
 431   GetSplitOp(N->getOperand(1), Lo, Hi);
 432
 433   unsigned IncrementSize = Lo.getValueType().getSizeInBits()/8;
 434
 435   Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset, isVol, Alignment);
 436
 437   // Increment the pointer to the other half.
 438   Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
 439                     DAG.getIntPtrConstant(IncrementSize));
 440
 441   Hi = DAG.getStore(Ch, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
 442                     isVol, MinAlign(Alignment, IncrementSize));
 443   return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
 444 }
 445
 446 SDOperand DAGTypeLegalizer::SplitOp_RET(SDNode *N, unsigned OpNo) {
 447   assert(N->getNumOperands() == 3 &&"Can only handle ret of one vector so far");
 448   // FIXME: Returns of gcc generic vectors larger than a legal vector
 449   // type should be returned by reference!
 450   SDOperand Lo, Hi;
 451   GetSplitOp(N->getOperand(1), Lo, Hi);
 452
 453   SDOperand Chain = N->getOperand(0);  // The chain.
 454   SDOperand Sign = N->getOperand(2);  // Signness
 455
 456   return DAG.getNode(ISD::RET, MVT::Other, Chain, Lo, Sign, Hi, Sign);
 457 }
 458
 459 SDOperand DAGTypeLegalizer::SplitOp_BIT_CONVERT(SDNode *N) {
 460   // For example, i64 = BIT_CONVERT v4i16 on alpha.  Typically the vector will
 461   // end up being split all the way down to individual components.  Convert the
 462   // split pieces into integers and reassemble.
 463   SDOperand Lo, Hi;
 464   GetSplitOp(N->getOperand(0), Lo, Hi);
 465   Lo = BitConvertToInteger(Lo);
 466   Hi = BitConvertToInteger(Hi);
 467
 468   if (TLI.isBigEndian())
 469     std::swap(Lo, Hi);
 470
 471   return DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0),
 472                      JoinIntegers(Lo, Hi));
 473 }
 474
 475 SDOperand DAGTypeLegalizer::SplitOp_EXTRACT_VECTOR_ELT(SDNode *N) {
 476   SDOperand Vec = N->getOperand(0);
 477   SDOperand Idx = N->getOperand(1);
 478   MVT VecVT = Vec.getValueType();
 479
 480   if (isa<ConstantSDNode>(Idx)) {
 481     uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getValue();
 482     assert(IdxVal < VecVT.getVectorNumElements() && "Invalid vector index!");
 483
 484     SDOperand Lo, Hi;
 485     GetSplitOp(Vec, Lo, Hi);
 486
 487     uint64_t LoElts = Lo.getValueType().getVectorNumElements();
 488
 489     if (IdxVal < LoElts)
 490       return DAG.UpdateNodeOperands(SDOperand(N, 0), Lo, Idx);
 491     else
 492       return DAG.UpdateNodeOperands(SDOperand(N, 0), Hi,
 493                                     DAG.getConstant(IdxVal - LoElts,
 494                                                     Idx.getValueType()));
 495   }
 496
 497   // Store the vector to the stack.
 498   MVT EltVT = VecVT.getVectorElementType();
 499   SDOperand StackPtr = DAG.CreateStackTemporary(VecVT);
 500   SDOperand Store = DAG.getStore(DAG.getEntryNode(), Vec, StackPtr, NULL, 0);
 501
 502   // Load back the required element.
 503   StackPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
 504   return DAG.getLoad(EltVT, Store, StackPtr, NULL, 0);
 505 }
 506
 507 SDOperand DAGTypeLegalizer::SplitOp_EXTRACT_SUBVECTOR(SDNode *N) {
 508   // We know that the extracted result type is legal.  For now, assume the index
 509   // is a constant.
 510   MVT SubVT = N->getValueType(0);
 511   SDOperand Idx = N->getOperand(1);
 512   SDOperand Lo, Hi;
 513   GetSplitOp(N->getOperand(0), Lo, Hi);
 514
 515   uint64_t LoElts = Lo.getValueType().getVectorNumElements();
 516   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getValue();
 517
 518   if (IdxVal < LoElts) {
 519     assert(IdxVal + SubVT.getVectorNumElements() <= LoElts &&
 520            "Extracted subvector crosses vector split!");
 521     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SubVT, Lo, Idx);
 522   } else {
 523     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SubVT, Hi,
 524                        DAG.getConstant(IdxVal - LoElts, Idx.getValueType()));
 525   }
 526 }
 527
 528 SDOperand DAGTypeLegalizer::SplitOp_VECTOR_SHUFFLE(SDNode *N, unsigned OpNo) {
 529   assert(OpNo == 2 && "Shuffle source type differs from result type?");
 530   SDOperand Mask = N->getOperand(2);
 531   unsigned MaskLength = Mask.getValueType().getVectorNumElements();
 532   unsigned LargestMaskEntryPlusOne = 2 * MaskLength;
 533   unsigned MinimumBitWidth = Log2_32_Ceil(LargestMaskEntryPlusOne);
 534
 535   // Look for a legal vector type to place the mask values in.
 536   // Note that there may not be *any* legal vector-of-integer
 537   // type for which the element type is legal!
 538   for (MVT::SimpleValueType EltVT = MVT::FIRST_INTEGER_VALUETYPE;
 539        EltVT <= MVT::LAST_INTEGER_VALUETYPE;
 540        // Integer values types are consecutively numbered.  Exploit this.
 541        EltVT = MVT::SimpleValueType(EltVT + 1)) {
 542
 543     // Is the element type big enough to hold the values?
 544     if (MVT(EltVT).getSizeInBits() < MinimumBitWidth)
 545       // Nope.
 546       continue;
 547
 548     // Is the vector type legal?
 549     MVT VecVT = MVT::getVectorVT(EltVT, MaskLength);
 550     if (!isTypeLegal(VecVT))
 551       // Nope.
 552       continue;
 553
 554     // If the element type is not legal, find a larger legal type to use for
 555     // the BUILD_VECTOR operands.  This is an ugly hack, but seems to work!
 556     // FIXME: The real solution is to change VECTOR_SHUFFLE into a variadic
 557     // node where the shuffle mask is a list of integer operands, #2 .. #2+n.
 558     for (MVT::SimpleValueType OpVT = EltVT; OpVT <= MVT::LAST_INTEGER_VALUETYPE;
 559          // Integer values types are consecutively numbered.  Exploit this.
 560          OpVT = MVT::SimpleValueType(OpVT + 1)) {
 561       if (!isTypeLegal(OpVT))
 562         continue;
 563
 564       // Success!  Rebuild the vector using the legal types.
 565       SmallVector<SDOperand, 16> Ops(MaskLength);
 566       for (unsigned i = 0; i < MaskLength; ++i) {
 567         uint64_t Idx =
 568           cast<ConstantSDNode>(Mask.getOperand(i))->getValue();
 569         Ops[i] = DAG.getConstant(Idx, OpVT);
 570       }
 571       return DAG.UpdateNodeOperands(SDOperand(N,0),
 572                                     N->getOperand(0), N->getOperand(1),
 573                                     DAG.getNode(ISD::BUILD_VECTOR,
 574                                                 VecVT, &Ops[0], Ops.size()));
 575     }
 576
 577     // Continuing is pointless - failure is certain.
 578     break;
 579   }
 580   assert(false && "Failed to find an appropriate mask type!");
 581   return SDOperand(N, 0);
 582 }