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