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