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