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 two vectors of half the size.  For example, implementing
  19 // <128 x f32> operations in terms of two <64 x f32> operations.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "LegalizeTypes.h"
  24 #include "llvm/IR/DataLayout.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 using namespace llvm;
  28
  29 //===----------------------------------------------------------------------===//
  30 //  Result Vector Scalarization: <1 x ty> -> ty.
  31 //===----------------------------------------------------------------------===//
  32
  33 void DAGTypeLegalizer::ScalarizeVectorResult(SDNode *N, unsigned ResNo) {
  34   DEBUG(dbgs() << "Scalarize node result " << ResNo << ": ";
  35         N->dump(&DAG);
  36         dbgs() << "\n");
  37   SDValue R = SDValue();
  38
  39   switch (N->getOpcode()) {
  40   default:
  41 #ifndef NDEBUG
  42     dbgs() << "ScalarizeVectorResult #" << ResNo << ": ";
  43     N->dump(&DAG);
  44     dbgs() << "\n";
  45 #endif
  46     report_fatal_error("Do not know how to scalarize the result of this "
  47                        "operator!\n");
  48
  49   case ISD::MERGE_VALUES:      R = ScalarizeVecRes_MERGE_VALUES(N, ResNo);break;
  50   case ISD::BITCAST:           R = ScalarizeVecRes_BITCAST(N); break;
  51   case ISD::BUILD_VECTOR:      R = ScalarizeVecRes_BUILD_VECTOR(N); break;
  52   case ISD::CONVERT_RNDSAT:    R = ScalarizeVecRes_CONVERT_RNDSAT(N); break;
  53   case ISD::EXTRACT_SUBVECTOR: R = ScalarizeVecRes_EXTRACT_SUBVECTOR(N); break;
  54   case ISD::FP_ROUND:          R = ScalarizeVecRes_FP_ROUND(N); break;
  55   case ISD::FP_ROUND_INREG:    R = ScalarizeVecRes_InregOp(N); break;
  56   case ISD::FPOWI:             R = ScalarizeVecRes_FPOWI(N); break;
  57   case ISD::INSERT_VECTOR_ELT: R = ScalarizeVecRes_INSERT_VECTOR_ELT(N); break;
  58   case ISD::LOAD:           R = ScalarizeVecRes_LOAD(cast<LoadSDNode>(N));break;
  59   case ISD::SCALAR_TO_VECTOR:  R = ScalarizeVecRes_SCALAR_TO_VECTOR(N); break;
  60   case ISD::SIGN_EXTEND_INREG: R = ScalarizeVecRes_InregOp(N); break;
  61   case ISD::VSELECT:           R = ScalarizeVecRes_VSELECT(N); break;
  62   case ISD::SELECT:            R = ScalarizeVecRes_SELECT(N); break;
  63   case ISD::SELECT_CC:         R = ScalarizeVecRes_SELECT_CC(N); break;
  64   case ISD::SETCC:             R = ScalarizeVecRes_SETCC(N); break;
  65   case ISD::UNDEF:             R = ScalarizeVecRes_UNDEF(N); break;
  66   case ISD::VECTOR_SHUFFLE:    R = ScalarizeVecRes_VECTOR_SHUFFLE(N); break;
  67   case ISD::ANY_EXTEND:
  68   case ISD::CTLZ:
  69   case ISD::CTPOP:
  70   case ISD::CTTZ:
  71   case ISD::FABS:
  72   case ISD::FCEIL:
  73   case ISD::FCOS:
  74   case ISD::FEXP:
  75   case ISD::FEXP2:
  76   case ISD::FFLOOR:
  77   case ISD::FLOG:
  78   case ISD::FLOG10:
  79   case ISD::FLOG2:
  80   case ISD::FNEARBYINT:
  81   case ISD::FNEG:
  82   case ISD::FP_EXTEND:
  83   case ISD::FP_TO_SINT:
  84   case ISD::FP_TO_UINT:
  85   case ISD::FRINT:
  86   case ISD::FROUND:
  87   case ISD::FSIN:
  88   case ISD::FSQRT:
  89   case ISD::FTRUNC:
  90   case ISD::SIGN_EXTEND:
  91   case ISD::SINT_TO_FP:
  92   case ISD::TRUNCATE:
  93   case ISD::UINT_TO_FP:
  94   case ISD::ZERO_EXTEND:
  95     R = ScalarizeVecRes_UnaryOp(N);
  96     break;
  97
  98   case ISD::ADD:
  99   case ISD::AND:
 100   case ISD::FADD:
 101   case ISD::FCOPYSIGN:
 102   case ISD::FDIV:
 103   case ISD::FMUL:
 104   case ISD::FPOW:
 105   case ISD::FREM:
 106   case ISD::FSUB:
 107   case ISD::MUL:
 108   case ISD::OR:
 109   case ISD::SDIV:
 110   case ISD::SREM:
 111   case ISD::SUB:
 112   case ISD::UDIV:
 113   case ISD::UREM:
 114   case ISD::XOR:
 115   case ISD::SHL:
 116   case ISD::SRA:
 117   case ISD::SRL:
 118     R = ScalarizeVecRes_BinOp(N);
 119     break;
 120   case ISD::FMA:
 121     R = ScalarizeVecRes_TernaryOp(N);
 122     break;
 123   }
 124
 125   // If R is null, the sub-method took care of registering the result.
 126   if (R.getNode())
 127     SetScalarizedVector(SDValue(N, ResNo), R);
 128 }
 129
 130 SDValue DAGTypeLegalizer::ScalarizeVecRes_BinOp(SDNode *N) {
 131   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 132   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 133   return DAG.getNode(N->getOpcode(), SDLoc(N),
 134                      LHS.getValueType(), LHS, RHS);
 135 }
 136
 137 SDValue DAGTypeLegalizer::ScalarizeVecRes_TernaryOp(SDNode *N) {
 138   SDValue Op0 = GetScalarizedVector(N->getOperand(0));
 139   SDValue Op1 = GetScalarizedVector(N->getOperand(1));
 140   SDValue Op2 = GetScalarizedVector(N->getOperand(2));
 141   return DAG.getNode(N->getOpcode(), SDLoc(N),
 142                      Op0.getValueType(), Op0, Op1, Op2);
 143 }
 144
 145 SDValue DAGTypeLegalizer::ScalarizeVecRes_MERGE_VALUES(SDNode *N,
 146                                                        unsigned ResNo) {
 147   SDValue Op = DisintegrateMERGE_VALUES(N, ResNo);
 148   return GetScalarizedVector(Op);
 149 }
 150
 151 SDValue DAGTypeLegalizer::ScalarizeVecRes_BITCAST(SDNode *N) {
 152   EVT NewVT = N->getValueType(0).getVectorElementType();
 153   return DAG.getNode(ISD::BITCAST, SDLoc(N),
 154                      NewVT, N->getOperand(0));
 155 }
 156
 157 SDValue DAGTypeLegalizer::ScalarizeVecRes_BUILD_VECTOR(SDNode *N) {
 158   EVT EltVT = N->getValueType(0).getVectorElementType();
 159   SDValue InOp = N->getOperand(0);
 160   // The BUILD_VECTOR operands may be of wider element types and
 161   // we may need to truncate them back to the requested return type.
 162   if (EltVT.isInteger())
 163     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
 164   return InOp;
 165 }
 166
 167 SDValue DAGTypeLegalizer::ScalarizeVecRes_CONVERT_RNDSAT(SDNode *N) {
 168   EVT NewVT = N->getValueType(0).getVectorElementType();
 169   SDValue Op0 = GetScalarizedVector(N->getOperand(0));
 170   return DAG.getConvertRndSat(NewVT, SDLoc(N),
 171                               Op0, DAG.getValueType(NewVT),
 172                               DAG.getValueType(Op0.getValueType()),
 173                               N->getOperand(3),
 174                               N->getOperand(4),
 175                               cast<CvtRndSatSDNode>(N)->getCvtCode());
 176 }
 177
 178 SDValue DAGTypeLegalizer::ScalarizeVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
 179   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
 180                      N->getValueType(0).getVectorElementType(),
 181                      N->getOperand(0), N->getOperand(1));
 182 }
 183
 184 SDValue DAGTypeLegalizer::ScalarizeVecRes_FP_ROUND(SDNode *N) {
 185   EVT NewVT = N->getValueType(0).getVectorElementType();
 186   SDValue Op = GetScalarizedVector(N->getOperand(0));
 187   return DAG.getNode(ISD::FP_ROUND, SDLoc(N),
 188                      NewVT, Op, N->getOperand(1));
 189 }
 190
 191 SDValue DAGTypeLegalizer::ScalarizeVecRes_FPOWI(SDNode *N) {
 192   SDValue Op = GetScalarizedVector(N->getOperand(0));
 193   return DAG.getNode(ISD::FPOWI, SDLoc(N),
 194                      Op.getValueType(), Op, N->getOperand(1));
 195 }
 196
 197 SDValue DAGTypeLegalizer::ScalarizeVecRes_INSERT_VECTOR_ELT(SDNode *N) {
 198   // The value to insert may have a wider type than the vector element type,
 199   // so be sure to truncate it to the element type if necessary.
 200   SDValue Op = N->getOperand(1);
 201   EVT EltVT = N->getValueType(0).getVectorElementType();
 202   if (Op.getValueType() != EltVT)
 203     // FIXME: Can this happen for floating point types?
 204     Op = DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, Op);
 205   return Op;
 206 }
 207
 208 SDValue DAGTypeLegalizer::ScalarizeVecRes_LOAD(LoadSDNode *N) {
 209   assert(N->isUnindexed() && "Indexed vector load?");
 210
 211   SDValue Result = DAG.getLoad(ISD::UNINDEXED,
 212                                N->getExtensionType(),
 213                                N->getValueType(0).getVectorElementType(),
 214                                SDLoc(N),
 215                                N->getChain(), N->getBasePtr(),
 216                                DAG.getUNDEF(N->getBasePtr().getValueType()),
 217                                N->getPointerInfo(),
 218                                N->getMemoryVT().getVectorElementType(),
 219                                N->isVolatile(), N->isNonTemporal(),
 220                                N->isInvariant(), N->getOriginalAlignment(),
 221                                N->getTBAAInfo());
 222
 223   // Legalized the chain result - switch anything that used the old chain to
 224   // use the new one.
 225   ReplaceValueWith(SDValue(N, 1), Result.getValue(1));
 226   return Result;
 227 }
 228
 229 SDValue DAGTypeLegalizer::ScalarizeVecRes_UnaryOp(SDNode *N) {
 230   // Get the dest type - it doesn't always match the input type, e.g. int_to_fp.
 231   EVT DestVT = N->getValueType(0).getVectorElementType();
 232   SDValue Op = GetScalarizedVector(N->getOperand(0));
 233   return DAG.getNode(N->getOpcode(), SDLoc(N), DestVT, Op);
 234 }
 235
 236 SDValue DAGTypeLegalizer::ScalarizeVecRes_InregOp(SDNode *N) {
 237   EVT EltVT = N->getValueType(0).getVectorElementType();
 238   EVT ExtVT = cast<VTSDNode>(N->getOperand(1))->getVT().getVectorElementType();
 239   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 240   return DAG.getNode(N->getOpcode(), SDLoc(N), EltVT,
 241                      LHS, DAG.getValueType(ExtVT));
 242 }
 243
 244 SDValue DAGTypeLegalizer::ScalarizeVecRes_SCALAR_TO_VECTOR(SDNode *N) {
 245   // If the operand is wider than the vector element type then it is implicitly
 246   // truncated.  Make that explicit here.
 247   EVT EltVT = N->getValueType(0).getVectorElementType();
 248   SDValue InOp = N->getOperand(0);
 249   if (InOp.getValueType() != EltVT)
 250     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
 251   return InOp;
 252 }
 253
 254 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSELECT(SDNode *N) {
 255   SDValue Cond = GetScalarizedVector(N->getOperand(0));
 256   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 257   TargetLowering::BooleanContent ScalarBool = TLI.getBooleanContents(false);
 258   TargetLowering::BooleanContent VecBool = TLI.getBooleanContents(true);
 259   if (ScalarBool != VecBool) {
 260     EVT CondVT = Cond.getValueType();
 261     switch (ScalarBool) {
 262       case TargetLowering::UndefinedBooleanContent:
 263         break;
 264       case TargetLowering::ZeroOrOneBooleanContent:
 265         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
 266                VecBool == TargetLowering::ZeroOrNegativeOneBooleanContent);
 267         // Vector read from all ones, scalar expects a single 1 so mask.
 268         Cond = DAG.getNode(ISD::AND, SDLoc(N), CondVT,
 269                            Cond, DAG.getConstant(1, CondVT));
 270         break;
 271       case TargetLowering::ZeroOrNegativeOneBooleanContent:
 272         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
 273                VecBool == TargetLowering::ZeroOrOneBooleanContent);
 274         // Vector reads from a one, scalar from all ones so sign extend.
 275         Cond = DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N), CondVT,
 276                            Cond, DAG.getValueType(MVT::i1));
 277         break;
 278     }
 279   }
 280
 281   return DAG.getSelect(SDLoc(N),
 282                        LHS.getValueType(), Cond, LHS,
 283                        GetScalarizedVector(N->getOperand(2)));
 284 }
 285
 286 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT(SDNode *N) {
 287   SDValue LHS = GetScalarizedVector(N->getOperand(1));
 288   return DAG.getSelect(SDLoc(N),
 289                        LHS.getValueType(), N->getOperand(0), LHS,
 290                        GetScalarizedVector(N->getOperand(2)));
 291 }
 292
 293 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT_CC(SDNode *N) {
 294   SDValue LHS = GetScalarizedVector(N->getOperand(2));
 295   return DAG.getNode(ISD::SELECT_CC, SDLoc(N), LHS.getValueType(),
 296                      N->getOperand(0), N->getOperand(1),
 297                      LHS, GetScalarizedVector(N->getOperand(3)),
 298                      N->getOperand(4));
 299 }
 300
 301 SDValue DAGTypeLegalizer::ScalarizeVecRes_SETCC(SDNode *N) {
 302   assert(N->getValueType(0).isVector() ==
 303          N->getOperand(0).getValueType().isVector() &&
 304          "Scalar/Vector type mismatch");
 305
 306   if (N->getValueType(0).isVector()) return ScalarizeVecRes_VSETCC(N);
 307
 308   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 309   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 310   SDLoc DL(N);
 311
 312   // Turn it into a scalar SETCC.
 313   return DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS, N->getOperand(2));
 314 }
 315
 316 SDValue DAGTypeLegalizer::ScalarizeVecRes_UNDEF(SDNode *N) {
 317   return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
 318 }
 319
 320 SDValue DAGTypeLegalizer::ScalarizeVecRes_VECTOR_SHUFFLE(SDNode *N) {
 321   // Figure out if the scalar is the LHS or RHS and return it.
 322   SDValue Arg = N->getOperand(2).getOperand(0);
 323   if (Arg.getOpcode() == ISD::UNDEF)
 324     return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
 325   unsigned Op = !cast<ConstantSDNode>(Arg)->isNullValue();
 326   return GetScalarizedVector(N->getOperand(Op));
 327 }
 328
 329 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSETCC(SDNode *N) {
 330   assert(N->getValueType(0).isVector() &&
 331          N->getOperand(0).getValueType().isVector() &&
 332          "Operand types must be vectors");
 333
 334   SDValue LHS = GetScalarizedVector(N->getOperand(0));
 335   SDValue RHS = GetScalarizedVector(N->getOperand(1));
 336   EVT NVT = N->getValueType(0).getVectorElementType();
 337   SDLoc DL(N);
 338
 339   // Turn it into a scalar SETCC.
 340   SDValue Res = DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS,
 341                             N->getOperand(2));
 342   // Vectors may have a different boolean contents to scalars.  Promote the
 343   // value appropriately.
 344   ISD::NodeType ExtendCode =
 345     TargetLowering::getExtendForContent(TLI.getBooleanContents(true));
 346   return DAG.getNode(ExtendCode, DL, NVT, Res);
 347 }
 348
 349
 350 //===----------------------------------------------------------------------===//
 351 //  Operand Vector Scalarization <1 x ty> -> ty.
 352 //===----------------------------------------------------------------------===//
 353
 354 bool DAGTypeLegalizer::ScalarizeVectorOperand(SDNode *N, unsigned OpNo) {
 355   DEBUG(dbgs() << "Scalarize node operand " << OpNo << ": ";
 356         N->dump(&DAG);
 357         dbgs() << "\n");
 358   SDValue Res = SDValue();
 359
 360   if (Res.getNode() == 0) {
 361     switch (N->getOpcode()) {
 362     default:
 363 #ifndef NDEBUG
 364       dbgs() << "ScalarizeVectorOperand Op #" << OpNo << ": ";
 365       N->dump(&DAG);
 366       dbgs() << "\n";
 367 #endif
 368       llvm_unreachable("Do not know how to scalarize this operator's operand!");
 369     case ISD::BITCAST:
 370       Res = ScalarizeVecOp_BITCAST(N);
 371       break;
 372     case ISD::ANY_EXTEND:
 373     case ISD::ZERO_EXTEND:
 374     case ISD::SIGN_EXTEND:
 375     case ISD::TRUNCATE:
 376       Res = ScalarizeVecOp_UnaryOp(N);
 377       break;
 378     case ISD::CONCAT_VECTORS:
 379       Res = ScalarizeVecOp_CONCAT_VECTORS(N);
 380       break;
 381     case ISD::EXTRACT_VECTOR_ELT:
 382       Res = ScalarizeVecOp_EXTRACT_VECTOR_ELT(N);
 383       break;
 384     case ISD::STORE:
 385       Res = ScalarizeVecOp_STORE(cast<StoreSDNode>(N), OpNo);
 386       break;
 387     }
 388   }
 389
 390   // If the result is null, the sub-method took care of registering results etc.
 391   if (!Res.getNode()) return false;
 392
 393   // If the result is N, the sub-method updated N in place.  Tell the legalizer
 394   // core about this.
 395   if (Res.getNode() == N)
 396     return true;
 397
 398   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 399          "Invalid operand expansion");
 400
 401   ReplaceValueWith(SDValue(N, 0), Res);
 402   return false;
 403 }
 404
 405 /// ScalarizeVecOp_BITCAST - If the value to convert is a vector that needs
 406 /// to be scalarized, it must be <1 x ty>.  Convert the element instead.
 407 SDValue DAGTypeLegalizer::ScalarizeVecOp_BITCAST(SDNode *N) {
 408   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 409   return DAG.getNode(ISD::BITCAST, SDLoc(N),
 410                      N->getValueType(0), Elt);
 411 }
 412
 413 /// ScalarizeVecOp_EXTEND - If the value to extend is a vector that needs
 414 /// to be scalarized, it must be <1 x ty>.  Extend the element instead.
 415 SDValue DAGTypeLegalizer::ScalarizeVecOp_UnaryOp(SDNode *N) {
 416   assert(N->getValueType(0).getVectorNumElements() == 1 &&
 417          "Unexected vector type!");
 418   SDValue Elt = GetScalarizedVector(N->getOperand(0));
 419   SmallVector<SDValue, 1> Ops(1);
 420   Ops[0] = DAG.getNode(N->getOpcode(), SDLoc(N),
 421                        N->getValueType(0).getScalarType(), Elt);
 422   // Revectorize the result so the types line up with what the uses of this
 423   // expression expect.
 424   return DAG.getNode(ISD::BUILD_VECTOR, SDLoc(N), N->getValueType(0),
 425                      &Ops[0], 1);
 426 }
 427
 428 /// ScalarizeVecOp_CONCAT_VECTORS - The vectors to concatenate have length one -
 429 /// use a BUILD_VECTOR instead.
 430 SDValue DAGTypeLegalizer::ScalarizeVecOp_CONCAT_VECTORS(SDNode *N) {
 431   SmallVector<SDValue, 8> Ops(N->getNumOperands());
 432   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i)
 433     Ops[i] = GetScalarizedVector(N->getOperand(i));
 434   return DAG.getNode(ISD::BUILD_VECTOR, SDLoc(N), N->getValueType(0),
 435                      &Ops[0], Ops.size());
 436 }
 437
 438 /// ScalarizeVecOp_EXTRACT_VECTOR_ELT - If the input is a vector that needs to
 439 /// be scalarized, it must be <1 x ty>, so just return the element, ignoring the
 440 /// index.
 441 SDValue DAGTypeLegalizer::ScalarizeVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
 442   SDValue Res = GetScalarizedVector(N->getOperand(0));
 443   if (Res.getValueType() != N->getValueType(0))
 444     Res = DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), N->getValueType(0),
 445                       Res);
 446   return Res;
 447 }
 448
 449 /// ScalarizeVecOp_STORE - If the value to store is a vector that needs to be
 450 /// scalarized, it must be <1 x ty>.  Just store the element.
 451 SDValue DAGTypeLegalizer::ScalarizeVecOp_STORE(StoreSDNode *N, unsigned OpNo){
 452   assert(N->isUnindexed() && "Indexed store of one-element vector?");
 453   assert(OpNo == 1 && "Do not know how to scalarize this operand!");
 454   SDLoc dl(N);
 455
 456   if (N->isTruncatingStore())
 457     return DAG.getTruncStore(N->getChain(), dl,
 458                              GetScalarizedVector(N->getOperand(1)),
 459                              N->getBasePtr(), N->getPointerInfo(),
 460                              N->getMemoryVT().getVectorElementType(),
 461                              N->isVolatile(), N->isNonTemporal(),
 462                              N->getAlignment(), N->getTBAAInfo());
 463
 464   return DAG.getStore(N->getChain(), dl, GetScalarizedVector(N->getOperand(1)),
 465                       N->getBasePtr(), N->getPointerInfo(),
 466                       N->isVolatile(), N->isNonTemporal(),
 467                       N->getOriginalAlignment(), N->getTBAAInfo());
 468 }
 469
 470
 471 //===----------------------------------------------------------------------===//
 472 //  Result Vector Splitting
 473 //===----------------------------------------------------------------------===//
 474
 475 /// SplitVectorResult - This method is called when the specified result of the
 476 /// specified node is found to need vector splitting.  At this point, the node
 477 /// may also have invalid operands or may have other results that need
 478 /// legalization, we just know that (at least) one result needs vector
 479 /// splitting.
 480 void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) {
 481   DEBUG(dbgs() << "Split node result: ";
 482         N->dump(&DAG);
 483         dbgs() << "\n");
 484   SDValue Lo, Hi;
 485
 486   // See if the target wants to custom expand this node.
 487   if (CustomLowerNode(N, N->getValueType(ResNo), true))
 488     return;
 489
 490   switch (N->getOpcode()) {
 491   default:
 492 #ifndef NDEBUG
 493     dbgs() << "SplitVectorResult #" << ResNo << ": ";
 494     N->dump(&DAG);
 495     dbgs() << "\n";
 496 #endif
 497     report_fatal_error("Do not know how to split the result of this "
 498                        "operator!\n");
 499
 500   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, ResNo, Lo, Hi); break;
 501   case ISD::VSELECT:
 502   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
 503   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
 504   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
 505   case ISD::BITCAST:           SplitVecRes_BITCAST(N, Lo, Hi); break;
 506   case ISD::BUILD_VECTOR:      SplitVecRes_BUILD_VECTOR(N, Lo, Hi); break;
 507   case ISD::CONCAT_VECTORS:    SplitVecRes_CONCAT_VECTORS(N, Lo, Hi); break;
 508   case ISD::EXTRACT_SUBVECTOR: SplitVecRes_EXTRACT_SUBVECTOR(N, Lo, Hi); break;
 509   case ISD::FP_ROUND_INREG:    SplitVecRes_InregOp(N, Lo, Hi); break;
 510   case ISD::FPOWI:             SplitVecRes_FPOWI(N, Lo, Hi); break;
 511   case ISD::INSERT_VECTOR_ELT: SplitVecRes_INSERT_VECTOR_ELT(N, Lo, Hi); break;
 512   case ISD::SCALAR_TO_VECTOR:  SplitVecRes_SCALAR_TO_VECTOR(N, Lo, Hi); break;
 513   case ISD::SIGN_EXTEND_INREG: SplitVecRes_InregOp(N, Lo, Hi); break;
 514   case ISD::LOAD:
 515     SplitVecRes_LOAD(cast<LoadSDNode>(N), Lo, Hi);
 516     break;
 517   case ISD::SETCC:
 518     SplitVecRes_SETCC(N, Lo, Hi);
 519     break;
 520   case ISD::VECTOR_SHUFFLE:
 521     SplitVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N), Lo, Hi);
 522     break;
 523
 524   case ISD::CONVERT_RNDSAT:
 525   case ISD::CTLZ:
 526   case ISD::CTTZ:
 527   case ISD::CTLZ_ZERO_UNDEF:
 528   case ISD::CTTZ_ZERO_UNDEF:
 529   case ISD::CTPOP:
 530   case ISD::FABS:
 531   case ISD::FCEIL:
 532   case ISD::FCOS:
 533   case ISD::FEXP:
 534   case ISD::FEXP2:
 535   case ISD::FFLOOR:
 536   case ISD::FLOG:
 537   case ISD::FLOG10:
 538   case ISD::FLOG2:
 539   case ISD::FNEARBYINT:
 540   case ISD::FNEG:
 541   case ISD::FP_EXTEND:
 542   case ISD::FP_ROUND:
 543   case ISD::FP_TO_SINT:
 544   case ISD::FP_TO_UINT:
 545   case ISD::FRINT:
 546   case ISD::FROUND:
 547   case ISD::FSIN:
 548   case ISD::FSQRT:
 549   case ISD::FTRUNC:
 550   case ISD::SINT_TO_FP:
 551   case ISD::TRUNCATE:
 552   case ISD::UINT_TO_FP:
 553     SplitVecRes_UnaryOp(N, Lo, Hi);
 554     break;
 555
 556   case ISD::ANY_EXTEND:
 557   case ISD::SIGN_EXTEND:
 558   case ISD::ZERO_EXTEND:
 559     SplitVecRes_ExtendOp(N, Lo, Hi);
 560     break;
 561
 562   case ISD::ADD:
 563   case ISD::SUB:
 564   case ISD::MUL:
 565   case ISD::FADD:
 566   case ISD::FCOPYSIGN:
 567   case ISD::FSUB:
 568   case ISD::FMUL:
 569   case ISD::SDIV:
 570   case ISD::UDIV:
 571   case ISD::FDIV:
 572   case ISD::FPOW:
 573   case ISD::AND:
 574   case ISD::OR:
 575   case ISD::XOR:
 576   case ISD::SHL:
 577   case ISD::SRA:
 578   case ISD::SRL:
 579   case ISD::UREM:
 580   case ISD::SREM:
 581   case ISD::FREM:
 582     SplitVecRes_BinOp(N, Lo, Hi);
 583     break;
 584   case ISD::FMA:
 585     SplitVecRes_TernaryOp(N, Lo, Hi);
 586     break;
 587   }
 588
 589   // If Lo/Hi is null, the sub-method took care of registering results etc.
 590   if (Lo.getNode())
 591     SetSplitVector(SDValue(N, ResNo), Lo, Hi);
 592 }
 593
 594 void DAGTypeLegalizer::SplitVecRes_BinOp(SDNode *N, SDValue &Lo,
 595                                          SDValue &Hi) {
 596   SDValue LHSLo, LHSHi;
 597   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 598   SDValue RHSLo, RHSHi;
 599   GetSplitVector(N->getOperand(1), RHSLo, RHSHi);
 600   SDLoc dl(N);
 601
 602   Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo, RHSLo);
 603   Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi, RHSHi);
 604 }
 605
 606 void DAGTypeLegalizer::SplitVecRes_TernaryOp(SDNode *N, SDValue &Lo,
 607                                              SDValue &Hi) {
 608   SDValue Op0Lo, Op0Hi;
 609   GetSplitVector(N->getOperand(0), Op0Lo, Op0Hi);
 610   SDValue Op1Lo, Op1Hi;
 611   GetSplitVector(N->getOperand(1), Op1Lo, Op1Hi);
 612   SDValue Op2Lo, Op2Hi;
 613   GetSplitVector(N->getOperand(2), Op2Lo, Op2Hi);
 614   SDLoc dl(N);
 615
 616   Lo = DAG.getNode(N->getOpcode(), dl, Op0Lo.getValueType(),
 617                    Op0Lo, Op1Lo, Op2Lo);
 618   Hi = DAG.getNode(N->getOpcode(), dl, Op0Hi.getValueType(),
 619                    Op0Hi, Op1Hi, Op2Hi);
 620 }
 621
 622 void DAGTypeLegalizer::SplitVecRes_BITCAST(SDNode *N, SDValue &Lo,
 623                                            SDValue &Hi) {
 624   // We know the result is a vector.  The input may be either a vector or a
 625   // scalar value.
 626   EVT LoVT, HiVT;
 627   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 628   SDLoc dl(N);
 629
 630   SDValue InOp = N->getOperand(0);
 631   EVT InVT = InOp.getValueType();
 632
 633   // Handle some special cases efficiently.
 634   switch (getTypeAction(InVT)) {
 635   case TargetLowering::TypeLegal:
 636   case TargetLowering::TypePromoteInteger:
 637   case TargetLowering::TypeSoftenFloat:
 638   case TargetLowering::TypeScalarizeVector:
 639   case TargetLowering::TypeWidenVector:
 640     break;
 641   case TargetLowering::TypeExpandInteger:
 642   case TargetLowering::TypeExpandFloat:
 643     // A scalar to vector conversion, where the scalar needs expansion.
 644     // If the vector is being split in two then we can just convert the
 645     // expanded pieces.
 646     if (LoVT == HiVT) {
 647       GetExpandedOp(InOp, Lo, Hi);
 648       if (TLI.isBigEndian())
 649         std::swap(Lo, Hi);
 650       Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 651       Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 652       return;
 653     }
 654     break;
 655   case TargetLowering::TypeSplitVector:
 656     // If the input is a vector that needs to be split, convert each split
 657     // piece of the input now.
 658     GetSplitVector(InOp, Lo, Hi);
 659     Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 660     Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 661     return;
 662   }
 663
 664   // In the general case, convert the input to an integer and split it by hand.
 665   EVT LoIntVT = EVT::getIntegerVT(*DAG.getContext(), LoVT.getSizeInBits());
 666   EVT HiIntVT = EVT::getIntegerVT(*DAG.getContext(), HiVT.getSizeInBits());
 667   if (TLI.isBigEndian())
 668     std::swap(LoIntVT, HiIntVT);
 669
 670   SplitInteger(BitConvertToInteger(InOp), LoIntVT, HiIntVT, Lo, Hi);
 671
 672   if (TLI.isBigEndian())
 673     std::swap(Lo, Hi);
 674   Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
 675   Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
 676 }
 677
 678 void DAGTypeLegalizer::SplitVecRes_BUILD_VECTOR(SDNode *N, SDValue &Lo,
 679                                                 SDValue &Hi) {
 680   EVT LoVT, HiVT;
 681   SDLoc dl(N);
 682   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 683   unsigned LoNumElts = LoVT.getVectorNumElements();
 684   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+LoNumElts);
 685   Lo = DAG.getNode(ISD::BUILD_VECTOR, dl, LoVT, &LoOps[0], LoOps.size());
 686
 687   SmallVector<SDValue, 8> HiOps(N->op_begin()+LoNumElts, N->op_end());
 688   Hi = DAG.getNode(ISD::BUILD_VECTOR, dl, HiVT, &HiOps[0], HiOps.size());
 689 }
 690
 691 void DAGTypeLegalizer::SplitVecRes_CONCAT_VECTORS(SDNode *N, SDValue &Lo,
 692                                                   SDValue &Hi) {
 693   assert(!(N->getNumOperands() & 1) && "Unsupported CONCAT_VECTORS");
 694   SDLoc dl(N);
 695   unsigned NumSubvectors = N->getNumOperands() / 2;
 696   if (NumSubvectors == 1) {
 697     Lo = N->getOperand(0);
 698     Hi = N->getOperand(1);
 699     return;
 700   }
 701
 702   EVT LoVT, HiVT;
 703   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 704
 705   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+NumSubvectors);
 706   Lo = DAG.getNode(ISD::CONCAT_VECTORS, dl, LoVT, &LoOps[0], LoOps.size());
 707
 708   SmallVector<SDValue, 8> HiOps(N->op_begin()+NumSubvectors, N->op_end());
 709   Hi = DAG.getNode(ISD::CONCAT_VECTORS, dl, HiVT, &HiOps[0], HiOps.size());
 710 }
 711
 712 void DAGTypeLegalizer::SplitVecRes_EXTRACT_SUBVECTOR(SDNode *N, SDValue &Lo,
 713                                                      SDValue &Hi) {
 714   SDValue Vec = N->getOperand(0);
 715   SDValue Idx = N->getOperand(1);
 716   SDLoc dl(N);
 717
 718   EVT LoVT, HiVT;
 719   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 720
 721   Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, LoVT, Vec, Idx);
 722   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
 723   Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, HiVT, Vec,
 724                    DAG.getConstant(IdxVal + LoVT.getVectorNumElements(),
 725                                    TLI.getVectorIdxTy()));
 726 }
 727
 728 void DAGTypeLegalizer::SplitVecRes_FPOWI(SDNode *N, SDValue &Lo,
 729                                          SDValue &Hi) {
 730   SDLoc dl(N);
 731   GetSplitVector(N->getOperand(0), Lo, Hi);
 732   Lo = DAG.getNode(ISD::FPOWI, dl, Lo.getValueType(), Lo, N->getOperand(1));
 733   Hi = DAG.getNode(ISD::FPOWI, dl, Hi.getValueType(), Hi, N->getOperand(1));
 734 }
 735
 736 void DAGTypeLegalizer::SplitVecRes_InregOp(SDNode *N, SDValue &Lo,
 737                                            SDValue &Hi) {
 738   SDValue LHSLo, LHSHi;
 739   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
 740   SDLoc dl(N);
 741
 742   EVT LoVT, HiVT;
 743   GetSplitDestVTs(cast<VTSDNode>(N->getOperand(1))->getVT(), LoVT, HiVT);
 744
 745   Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo,
 746                    DAG.getValueType(LoVT));
 747   Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi,
 748                    DAG.getValueType(HiVT));
 749 }
 750
 751 void DAGTypeLegalizer::SplitVecRes_INSERT_VECTOR_ELT(SDNode *N, SDValue &Lo,
 752                                                      SDValue &Hi) {
 753   SDValue Vec = N->getOperand(0);
 754   SDValue Elt = N->getOperand(1);
 755   SDValue Idx = N->getOperand(2);
 756   SDLoc dl(N);
 757   GetSplitVector(Vec, Lo, Hi);
 758
 759   if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
 760     unsigned IdxVal = CIdx->getZExtValue();
 761     unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
 762     if (IdxVal < LoNumElts)
 763       Lo = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl,
 764                        Lo.getValueType(), Lo, Elt, Idx);
 765     else
 766       Hi = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, Hi.getValueType(), Hi, Elt,
 767                        DAG.getConstant(IdxVal - LoNumElts,
 768                                        TLI.getVectorIdxTy()));
 769     return;
 770   }
 771
 772   // Spill the vector to the stack.
 773   EVT VecVT = Vec.getValueType();
 774   EVT EltVT = VecVT.getVectorElementType();
 775   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
 776   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr,
 777                                MachinePointerInfo(), false, false, 0);
 778
 779   // Store the new element.  This may be larger than the vector element type,
 780   // so use a truncating store.
 781   SDValue EltPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
 782   Type *VecType = VecVT.getTypeForEVT(*DAG.getContext());
 783   unsigned Alignment =
 784     TLI.getDataLayout()->getPrefTypeAlignment(VecType);
 785   Store = DAG.getTruncStore(Store, dl, Elt, EltPtr, MachinePointerInfo(), EltVT,
 786                             false, false, 0);
 787
 788   // Load the Lo part from the stack slot.
 789   Lo = DAG.getLoad(Lo.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
 790                    false, false, false, 0);
 791
 792   // Increment the pointer to the other part.
 793   unsigned IncrementSize = Lo.getValueType().getSizeInBits() / 8;
 794   StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 795                        DAG.getConstant(IncrementSize, StackPtr.getValueType()));
 796
 797   // Load the Hi part from the stack slot.
 798   Hi = DAG.getLoad(Hi.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
 799                    false, false, false, MinAlign(Alignment, IncrementSize));
 800 }
 801
 802 void DAGTypeLegalizer::SplitVecRes_SCALAR_TO_VECTOR(SDNode *N, SDValue &Lo,
 803                                                     SDValue &Hi) {
 804   EVT LoVT, HiVT;
 805   SDLoc dl(N);
 806   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 807   Lo = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, LoVT, N->getOperand(0));
 808   Hi = DAG.getUNDEF(HiVT);
 809 }
 810
 811 void DAGTypeLegalizer::SplitVecRes_LOAD(LoadSDNode *LD, SDValue &Lo,
 812                                         SDValue &Hi) {
 813   assert(ISD::isUNINDEXEDLoad(LD) && "Indexed load during type legalization!");
 814   EVT LoVT, HiVT;
 815   SDLoc dl(LD);
 816   GetSplitDestVTs(LD->getValueType(0), LoVT, HiVT);
 817
 818   ISD::LoadExtType ExtType = LD->getExtensionType();
 819   SDValue Ch = LD->getChain();
 820   SDValue Ptr = LD->getBasePtr();
 821   SDValue Offset = DAG.getUNDEF(Ptr.getValueType());
 822   EVT MemoryVT = LD->getMemoryVT();
 823   unsigned Alignment = LD->getOriginalAlignment();
 824   bool isVolatile = LD->isVolatile();
 825   bool isNonTemporal = LD->isNonTemporal();
 826   bool isInvariant = LD->isInvariant();
 827   const MDNode *TBAAInfo = LD->getTBAAInfo();
 828
 829   EVT LoMemVT, HiMemVT;
 830   GetSplitDestVTs(MemoryVT, LoMemVT, HiMemVT);
 831
 832   Lo = DAG.getLoad(ISD::UNINDEXED, ExtType, LoVT, dl, Ch, Ptr, Offset,
 833                    LD->getPointerInfo(), LoMemVT, isVolatile, isNonTemporal,
 834                    isInvariant, Alignment, TBAAInfo);
 835
 836   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
 837   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 838                     DAG.getConstant(IncrementSize, Ptr.getValueType()));
 839   Hi = DAG.getLoad(ISD::UNINDEXED, ExtType, HiVT, dl, Ch, Ptr, Offset,
 840                    LD->getPointerInfo().getWithOffset(IncrementSize),
 841                    HiMemVT, isVolatile, isNonTemporal, isInvariant, Alignment,
 842                    TBAAInfo);
 843
 844   // Build a factor node to remember that this load is independent of the
 845   // other one.
 846   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
 847                    Hi.getValue(1));
 848
 849   // Legalized the chain result - switch anything that used the old chain to
 850   // use the new one.
 851   ReplaceValueWith(SDValue(LD, 1), Ch);
 852 }
 853
 854 void DAGTypeLegalizer::SplitVecRes_SETCC(SDNode *N, SDValue &Lo, SDValue &Hi) {
 855   assert(N->getValueType(0).isVector() &&
 856          N->getOperand(0).getValueType().isVector() &&
 857          "Operand types must be vectors");
 858
 859   EVT LoVT, HiVT;
 860   SDLoc DL(N);
 861   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 862
 863   // Split the input.
 864   EVT InVT = N->getOperand(0).getValueType();
 865   SDValue LL, LH, RL, RH;
 866   EVT InNVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(),
 867                                LoVT.getVectorNumElements());
 868   LL = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(0),
 869                    DAG.getConstant(0, TLI.getVectorIdxTy()));
 870   LH = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(0),
 871                    DAG.getConstant(InNVT.getVectorNumElements(),
 872                    TLI.getVectorIdxTy()));
 873
 874   RL = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(1),
 875                    DAG.getConstant(0, TLI.getVectorIdxTy()));
 876   RH = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InNVT, N->getOperand(1),
 877                    DAG.getConstant(InNVT.getVectorNumElements(),
 878                    TLI.getVectorIdxTy()));
 879
 880   Lo = DAG.getNode(N->getOpcode(), DL, LoVT, LL, RL, N->getOperand(2));
 881   Hi = DAG.getNode(N->getOpcode(), DL, HiVT, LH, RH, N->getOperand(2));
 882 }
 883
 884 void DAGTypeLegalizer::SplitVecRes_UnaryOp(SDNode *N, SDValue &Lo,
 885                                            SDValue &Hi) {
 886   // Get the dest types - they may not match the input types, e.g. int_to_fp.
 887   EVT LoVT, HiVT;
 888   SDLoc dl(N);
 889   GetSplitDestVTs(N->getValueType(0), LoVT, HiVT);
 890
 891   // If the input also splits, handle it directly for a compile time speedup.
 892   // Otherwise split it by hand.
 893   EVT InVT = N->getOperand(0).getValueType();
 894   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector) {
 895     GetSplitVector(N->getOperand(0), Lo, Hi);
 896   } else {
 897     EVT InNVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(),
 898                                  LoVT.getVectorNumElements());
 899     Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, InNVT, N->getOperand(0),
 900                      DAG.getConstant(0, TLI.getVectorIdxTy()));
 901     Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, InNVT, N->getOperand(0),
 902                      DAG.getConstant(InNVT.getVectorNumElements(),
 903                                      TLI.getVectorIdxTy()));
 904   }
 905
 906   if (N->getOpcode() == ISD::FP_ROUND) {
 907     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo, N->getOperand(1));
 908     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi, N->getOperand(1));
 909   } else if (N->getOpcode() == ISD::CONVERT_RNDSAT) {
 910     SDValue DTyOpLo = DAG.getValueType(LoVT);
 911     SDValue DTyOpHi = DAG.getValueType(HiVT);
 912     SDValue STyOpLo = DAG.getValueType(Lo.getValueType());
 913     SDValue STyOpHi = DAG.getValueType(Hi.getValueType());
 914     SDValue RndOp = N->getOperand(3);
 915     SDValue SatOp = N->getOperand(4);
 916     ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
 917     Lo = DAG.getConvertRndSat(LoVT, dl, Lo, DTyOpLo, STyOpLo, RndOp, SatOp,
 918                               CvtCode);
 919     Hi = DAG.getConvertRndSat(HiVT, dl, Hi, DTyOpHi, STyOpHi, RndOp, SatOp,
 920                               CvtCode);
 921   } else {
 922     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
 923     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
 924   }
 925 }
 926
 927 void DAGTypeLegalizer::SplitVecRes_ExtendOp(SDNode *N, SDValue &Lo,
 928                                             SDValue &Hi) {
 929   SDLoc dl(N);
 930   EVT SrcVT = N->getOperand(0).getValueType();
 931   EVT DestVT = N->getValueType(0);
 932   EVT LoVT, HiVT;
 933   GetSplitDestVTs(DestVT, LoVT, HiVT);
 934
 935   // We can do better than a generic split operation if the extend is doing
 936   // more than just doubling the width of the elements and the following are
 937   // true:
 938   //   - The number of vector elements is even,
 939   //   - the source type is legal,
 940   //   - the type of a split source is illegal,
 941   //   - the type of an extended (by doubling element size) source is legal, and
 942   //   - the type of that extended source when split is legal.
 943   //
 944   // This won't necessarily completely legalize the operation, but it will
 945   // more effectively move in the right direction and prevent falling down
 946   // to scalarization in many cases due to the input vector being split too
 947   // far.
 948   unsigned NumElements = SrcVT.getVectorNumElements();
 949   if ((NumElements & 1) == 0 &&
 950       SrcVT.getSizeInBits() * 2 < DestVT.getSizeInBits()) {
 951     LLVMContext &Ctx = *DAG.getContext();
 952     EVT NewSrcVT = EVT::getVectorVT(
 953         Ctx, EVT::getIntegerVT(
 954                  Ctx, SrcVT.getVectorElementType().getSizeInBits() * 2),
 955         NumElements);
 956     EVT SplitSrcVT =
 957         EVT::getVectorVT(Ctx, SrcVT.getVectorElementType(), NumElements / 2);
 958     EVT SplitLoVT, SplitHiVT;
 959     GetSplitDestVTs(NewSrcVT, SplitLoVT, SplitHiVT);
 960     if (TLI.isTypeLegal(SrcVT) && !TLI.isTypeLegal(SplitSrcVT) &&
 961         TLI.isTypeLegal(NewSrcVT) && TLI.isTypeLegal(SplitLoVT)) {
 962       DEBUG(dbgs() << "Split vector extend via incremental extend:";
 963             N->dump(&DAG); dbgs() << "\n");
 964       // Extend the source vector by one step.
 965       SDValue NewSrc =
 966           DAG.getNode(N->getOpcode(), dl, NewSrcVT, N->getOperand(0));
 967       // Get the low and high halves of the new, extended one step, vector.
 968       Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SplitLoVT, NewSrc,
 969                        DAG.getConstant(0, TLI.getVectorIdxTy()));
 970       Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SplitHiVT, NewSrc,
 971                        DAG.getConstant(SplitLoVT.getVectorNumElements(),
 972                                        TLI.getVectorIdxTy()));
 973       // Extend those vector halves the rest of the way.
 974       Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
 975       Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
 976       return;
 977     }
 978   }
 979   // Fall back to the generic unary operator splitting otherwise.
 980   SplitVecRes_UnaryOp(N, Lo, Hi);
 981 }
 982
 983 void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N,
 984                                                   SDValue &Lo, SDValue &Hi) {
 985   // The low and high parts of the original input give four input vectors.
 986   SDValue Inputs[4];
 987   SDLoc dl(N);
 988   GetSplitVector(N->getOperand(0), Inputs[0], Inputs[1]);
 989   GetSplitVector(N->getOperand(1), Inputs[2], Inputs[3]);
 990   EVT NewVT = Inputs[0].getValueType();
 991   unsigned NewElts = NewVT.getVectorNumElements();
 992
 993   // If Lo or Hi uses elements from at most two of the four input vectors, then
 994   // express it as a vector shuffle of those two inputs.  Otherwise extract the
 995   // input elements by hand and construct the Lo/Hi output using a BUILD_VECTOR.
 996   SmallVector<int, 16> Ops;
 997   for (unsigned High = 0; High < 2; ++High) {
 998     SDValue &Output = High ? Hi : Lo;
 999
1000     // Build a shuffle mask for the output, discovering on the fly which
1001     // input vectors to use as shuffle operands (recorded in InputUsed).
1002     // If building a suitable shuffle vector proves too hard, then bail
1003     // out with useBuildVector set.
1004     unsigned InputUsed[2] = { -1U, -1U }; // Not yet discovered.
1005     unsigned FirstMaskIdx = High * NewElts;
1006     bool useBuildVector = false;
1007     for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
1008       // The mask element.  This indexes into the input.
1009       int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
1010
1011       // The input vector this mask element indexes into.
1012       unsigned Input = (unsigned)Idx / NewElts;
1013
1014       if (Input >= array_lengthof(Inputs)) {
1015         // The mask element does not index into any input vector.
1016         Ops.push_back(-1);
1017         continue;
1018       }
1019
1020       // Turn the index into an offset from the start of the input vector.
1021       Idx -= Input * NewElts;
1022
1023       // Find or create a shuffle vector operand to hold this input.
1024       unsigned OpNo;
1025       for (OpNo = 0; OpNo < array_lengthof(InputUsed); ++OpNo) {
1026         if (InputUsed[OpNo] == Input) {
1027           // This input vector is already an operand.
1028           break;
1029         } else if (InputUsed[OpNo] == -1U) {
1030           // Create a new operand for this input vector.
1031           InputUsed[OpNo] = Input;
1032           break;
1033         }
1034       }
1035
1036       if (OpNo >= array_lengthof(InputUsed)) {
1037         // More than two input vectors used!  Give up on trying to create a
1038         // shuffle vector.  Insert all elements into a BUILD_VECTOR instead.
1039         useBuildVector = true;
1040         break;
1041       }
1042
1043       // Add the mask index for the new shuffle vector.
1044       Ops.push_back(Idx + OpNo * NewElts);
1045     }
1046
1047     if (useBuildVector) {
1048       EVT EltVT = NewVT.getVectorElementType();
1049       SmallVector<SDValue, 16> SVOps;
1050
1051       // Extract the input elements by hand.
1052       for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
1053         // The mask element.  This indexes into the input.
1054         int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
1055
1056         // The input vector this mask element indexes into.
1057         unsigned Input = (unsigned)Idx / NewElts;
1058
1059         if (Input >= array_lengthof(Inputs)) {
1060           // The mask element is "undef" or indexes off the end of the input.
1061           SVOps.push_back(DAG.getUNDEF(EltVT));
1062           continue;
1063         }
1064
1065         // Turn the index into an offset from the start of the input vector.
1066         Idx -= Input * NewElts;
1067
1068         // Extract the vector element by hand.
1069         SVOps.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT,
1070                                     Inputs[Input], DAG.getConstant(Idx,
1071                                                    TLI.getVectorIdxTy())));
1072       }
1073
1074       // Construct the Lo/Hi output using a BUILD_VECTOR.
1075       Output = DAG.getNode(ISD::BUILD_VECTOR,dl,NewVT, &SVOps[0], SVOps.size());
1076     } else if (InputUsed[0] == -1U) {
1077       // No input vectors were used!  The result is undefined.
1078       Output = DAG.getUNDEF(NewVT);
1079     } else {
1080       SDValue Op0 = Inputs[InputUsed[0]];
1081       // If only one input was used, use an undefined vector for the other.
1082       SDValue Op1 = InputUsed[1] == -1U ?
1083         DAG.getUNDEF(NewVT) : Inputs[InputUsed[1]];
1084       // At least one input vector was used.  Create a new shuffle vector.
1085       Output =  DAG.getVectorShuffle(NewVT, dl, Op0, Op1, &Ops[0]);
1086     }
1087
1088     Ops.clear();
1089   }
1090 }
1091
1092
1093 //===----------------------------------------------------------------------===//
1094 //  Operand Vector Splitting
1095 //===----------------------------------------------------------------------===//
1096
1097 /// SplitVectorOperand - This method is called when the specified operand of the
1098 /// specified node is found to need vector splitting.  At this point, all of the
1099 /// result types of the node are known to be legal, but other operands of the
1100 /// node may need legalization as well as the specified one.
1101 bool DAGTypeLegalizer::SplitVectorOperand(SDNode *N, unsigned OpNo) {
1102   DEBUG(dbgs() << "Split node operand: ";
1103         N->dump(&DAG);
1104         dbgs() << "\n");
1105   SDValue Res = SDValue();
1106
1107   // See if the target wants to custom split this node.
1108   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
1109     return false;
1110
1111   if (Res.getNode() == 0) {
1112     switch (N->getOpcode()) {
1113     default:
1114 #ifndef NDEBUG
1115       dbgs() << "SplitVectorOperand Op #" << OpNo << ": ";
1116       N->dump(&DAG);
1117       dbgs() << "\n";
1118 #endif
1119       report_fatal_error("Do not know how to split this operator's "
1120                          "operand!\n");
1121
1122     case ISD::SETCC:             Res = SplitVecOp_VSETCC(N); break;
1123     case ISD::BITCAST:           Res = SplitVecOp_BITCAST(N); break;
1124     case ISD::EXTRACT_SUBVECTOR: Res = SplitVecOp_EXTRACT_SUBVECTOR(N); break;
1125     case ISD::EXTRACT_VECTOR_ELT:Res = SplitVecOp_EXTRACT_VECTOR_ELT(N); break;
1126     case ISD::CONCAT_VECTORS:    Res = SplitVecOp_CONCAT_VECTORS(N); break;
1127     case ISD::TRUNCATE:          Res = SplitVecOp_TRUNCATE(N); break;
1128     case ISD::FP_ROUND:          Res = SplitVecOp_FP_ROUND(N); break;
1129     case ISD::STORE:
1130       Res = SplitVecOp_STORE(cast<StoreSDNode>(N), OpNo);
1131       break;
1132     case ISD::VSELECT:
1133       Res = SplitVecOp_VSELECT(N, OpNo);
1134       break;
1135     case ISD::CTTZ:
1136     case ISD::CTLZ:
1137     case ISD::CTPOP:
1138     case ISD::FP_EXTEND:
1139     case ISD::FP_TO_SINT:
1140     case ISD::FP_TO_UINT:
1141     case ISD::SINT_TO_FP:
1142     case ISD::UINT_TO_FP:
1143     case ISD::FTRUNC:
1144     case ISD::SIGN_EXTEND:
1145     case ISD::ZERO_EXTEND:
1146     case ISD::ANY_EXTEND:
1147       Res = SplitVecOp_UnaryOp(N);
1148       break;
1149     }
1150   }
1151
1152   // If the result is null, the sub-method took care of registering results etc.
1153   if (!Res.getNode()) return false;
1154
1155   // If the result is N, the sub-method updated N in place.  Tell the legalizer
1156   // core about this.
1157   if (Res.getNode() == N)
1158     return true;
1159
1160   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1161          "Invalid operand expansion");
1162
1163   ReplaceValueWith(SDValue(N, 0), Res);
1164   return false;
1165 }
1166
1167 SDValue DAGTypeLegalizer::SplitVecOp_VSELECT(SDNode *N, unsigned OpNo) {
1168   // The only possibility for an illegal operand is the mask, since result type
1169   // legalization would have handled this node already otherwise.
1170   assert(OpNo == 0 && "Illegal operand must be mask");
1171
1172   SDValue Mask = N->getOperand(0);
1173   SDValue Src0 = N->getOperand(1);
1174   SDValue Src1 = N->getOperand(2);
1175   SDLoc DL(N);
1176   EVT MaskVT = Mask.getValueType();
1177   assert(MaskVT.isVector() && "VSELECT without a vector mask?");
1178
1179   SDValue Lo, Hi;
1180   GetSplitVector(N->getOperand(0), Lo, Hi);
1181   assert(Lo.getValueType() == Hi.getValueType() &&
1182          "Lo and Hi have differing types");
1183
1184   unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
1185   unsigned HiNumElts = Hi.getValueType().getVectorNumElements();
1186   assert(LoNumElts == HiNumElts && "Asymmetric vector split?");
1187
1188   LLVMContext &Ctx = *DAG.getContext();
1189   SDValue Zero = DAG.getConstant(0, TLI.getVectorIdxTy());
1190   SDValue LoElts = DAG.getConstant(LoNumElts, TLI.getVectorIdxTy());
1191   EVT Src0VT = Src0.getValueType();
1192   EVT Src0EltTy = Src0VT.getVectorElementType();
1193   EVT MaskEltTy = MaskVT.getVectorElementType();
1194
1195   EVT LoOpVT = EVT::getVectorVT(Ctx, Src0EltTy, LoNumElts);
1196   EVT LoMaskVT = EVT::getVectorVT(Ctx, MaskEltTy, LoNumElts);
1197   EVT HiOpVT = EVT::getVectorVT(Ctx, Src0EltTy, HiNumElts);
1198   EVT HiMaskVT = EVT::getVectorVT(Ctx, MaskEltTy, HiNumElts);
1199
1200   SDValue LoOp0 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, LoOpVT, Src0, Zero);
1201   SDValue LoOp1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, LoOpVT, Src1, Zero);
1202
1203   SDValue HiOp0 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, HiOpVT, Src0, LoElts);
1204   SDValue HiOp1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, HiOpVT, Src1, LoElts);
1205
1206   SDValue LoMask =
1207     DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, LoMaskVT, Mask, Zero);
1208   SDValue HiMask =
1209     DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, HiMaskVT, Mask, LoElts);
1210
1211   SDValue LoSelect =
1212     DAG.getNode(ISD::VSELECT, DL, LoOpVT, LoMask, LoOp0, LoOp1);
1213   SDValue HiSelect =
1214     DAG.getNode(ISD::VSELECT, DL, HiOpVT, HiMask, HiOp0, HiOp1);
1215
1216   return DAG.getNode(ISD::CONCAT_VECTORS, DL, Src0VT, LoSelect, HiSelect);
1217 }
1218
1219 SDValue DAGTypeLegalizer::SplitVecOp_UnaryOp(SDNode *N) {
1220   // The result has a legal vector type, but the input needs splitting.
1221   EVT ResVT = N->getValueType(0);
1222   SDValue Lo, Hi;
1223   SDLoc dl(N);
1224   GetSplitVector(N->getOperand(0), Lo, Hi);
1225   EVT InVT = Lo.getValueType();
1226
1227   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
1228                                InVT.getVectorNumElements());
1229
1230   Lo = DAG.getNode(N->getOpcode(), dl, OutVT, Lo);
1231   Hi = DAG.getNode(N->getOpcode(), dl, OutVT, Hi);
1232
1233   return DAG.getNode(ISD::CONCAT_VECTORS, dl, ResVT, Lo, Hi);
1234 }
1235
1236 SDValue DAGTypeLegalizer::SplitVecOp_BITCAST(SDNode *N) {
1237   // For example, i64 = BITCAST v4i16 on alpha.  Typically the vector will
1238   // end up being split all the way down to individual components.  Convert the
1239   // split pieces into integers and reassemble.
1240   SDValue Lo, Hi;
1241   GetSplitVector(N->getOperand(0), Lo, Hi);
1242   Lo = BitConvertToInteger(Lo);
1243   Hi = BitConvertToInteger(Hi);
1244
1245   if (TLI.isBigEndian())
1246     std::swap(Lo, Hi);
1247
1248   return DAG.getNode(ISD::BITCAST, SDLoc(N), N->getValueType(0),
1249                      JoinIntegers(Lo, Hi));
1250 }
1251
1252 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
1253   // We know that the extracted result type is legal.
1254   EVT SubVT = N->getValueType(0);
1255   SDValue Idx = N->getOperand(1);
1256   SDLoc dl(N);
1257   SDValue Lo, Hi;
1258   GetSplitVector(N->getOperand(0), Lo, Hi);
1259
1260   uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1261   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1262
1263   if (IdxVal < LoElts) {
1264     assert(IdxVal + SubVT.getVectorNumElements() <= LoElts &&
1265            "Extracted subvector crosses vector split!");
1266     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Lo, Idx);
1267   } else {
1268     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Hi,
1269                        DAG.getConstant(IdxVal - LoElts, Idx.getValueType()));
1270   }
1271 }
1272
1273 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
1274   SDValue Vec = N->getOperand(0);
1275   SDValue Idx = N->getOperand(1);
1276   EVT VecVT = Vec.getValueType();
1277
1278   if (isa<ConstantSDNode>(Idx)) {
1279     uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1280     assert(IdxVal < VecVT.getVectorNumElements() && "Invalid vector index!");
1281
1282     SDValue Lo, Hi;
1283     GetSplitVector(Vec, Lo, Hi);
1284
1285     uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1286
1287     if (IdxVal < LoElts)
1288       return SDValue(DAG.UpdateNodeOperands(N, Lo, Idx), 0);
1289     return SDValue(DAG.UpdateNodeOperands(N, Hi,
1290                                   DAG.getConstant(IdxVal - LoElts,
1291                                                   Idx.getValueType())), 0);
1292   }
1293
1294   // Store the vector to the stack.
1295   EVT EltVT = VecVT.getVectorElementType();
1296   SDLoc dl(N);
1297   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
1298   SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr,
1299                                MachinePointerInfo(), false, false, 0);
1300
1301   // Load back the required element.
1302   StackPtr = GetVectorElementPointer(StackPtr, EltVT, Idx);
1303   return DAG.getExtLoad(ISD::EXTLOAD, dl, N->getValueType(0), Store, StackPtr,
1304                         MachinePointerInfo(), EltVT, false, false, 0);
1305 }
1306
1307 SDValue DAGTypeLegalizer::SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo) {
1308   assert(N->isUnindexed() && "Indexed store of vector?");
1309   assert(OpNo == 1 && "Can only split the stored value");
1310   SDLoc DL(N);
1311
1312   bool isTruncating = N->isTruncatingStore();
1313   SDValue Ch  = N->getChain();
1314   SDValue Ptr = N->getBasePtr();
1315   EVT MemoryVT = N->getMemoryVT();
1316   unsigned Alignment = N->getOriginalAlignment();
1317   bool isVol = N->isVolatile();
1318   bool isNT = N->isNonTemporal();
1319   const MDNode *TBAAInfo = N->getTBAAInfo();
1320   SDValue Lo, Hi;
1321   GetSplitVector(N->getOperand(1), Lo, Hi);
1322
1323   EVT LoMemVT, HiMemVT;
1324   GetSplitDestVTs(MemoryVT, LoMemVT, HiMemVT);
1325
1326   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
1327
1328   if (isTruncating)
1329     Lo = DAG.getTruncStore(Ch, DL, Lo, Ptr, N->getPointerInfo(),
1330                            LoMemVT, isVol, isNT, Alignment, TBAAInfo);
1331   else
1332     Lo = DAG.getStore(Ch, DL, Lo, Ptr, N->getPointerInfo(),
1333                       isVol, isNT, Alignment, TBAAInfo);
1334
1335   // Increment the pointer to the other half.
1336   Ptr = DAG.getNode(ISD::ADD, DL, Ptr.getValueType(), Ptr,
1337                     DAG.getConstant(IncrementSize, Ptr.getValueType()));
1338
1339   if (isTruncating)
1340     Hi = DAG.getTruncStore(Ch, DL, Hi, Ptr,
1341                            N->getPointerInfo().getWithOffset(IncrementSize),
1342                            HiMemVT, isVol, isNT, Alignment, TBAAInfo);
1343   else
1344     Hi = DAG.getStore(Ch, DL, Hi, Ptr,
1345                       N->getPointerInfo().getWithOffset(IncrementSize),
1346                       isVol, isNT, Alignment, TBAAInfo);
1347
1348   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
1349 }
1350
1351 SDValue DAGTypeLegalizer::SplitVecOp_CONCAT_VECTORS(SDNode *N) {
1352   SDLoc DL(N);
1353
1354   // The input operands all must have the same type, and we know the result
1355   // type is valid.  Convert this to a buildvector which extracts all the
1356   // input elements.
1357   // TODO: If the input elements are power-two vectors, we could convert this to
1358   // a new CONCAT_VECTORS node with elements that are half-wide.
1359   SmallVector<SDValue, 32> Elts;
1360   EVT EltVT = N->getValueType(0).getVectorElementType();
1361   for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
1362     SDValue Op = N->getOperand(op);
1363     for (unsigned i = 0, e = Op.getValueType().getVectorNumElements();
1364          i != e; ++i) {
1365       Elts.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, EltVT,
1366                                  Op, DAG.getConstant(i, TLI.getVectorIdxTy())));
1367
1368     }
1369   }
1370
1371   return DAG.getNode(ISD::BUILD_VECTOR, DL, N->getValueType(0),
1372                      &Elts[0], Elts.size());
1373 }
1374
1375 SDValue DAGTypeLegalizer::SplitVecOp_TRUNCATE(SDNode *N) {
1376   // The result type is legal, but the input type is illegal.  If splitting
1377   // ends up with the result type of each half still being legal, just
1378   // do that.  If, however, that would result in an illegal result type,
1379   // we can try to get more clever with power-two vectors. Specifically,
1380   // split the input type, but also widen the result element size, then
1381   // concatenate the halves and truncate again.  For example, consider a target
1382   // where v8i8 is legal and v8i32 is not (ARM, which doesn't have 256-bit
1383   // vectors). To perform a "%res = v8i8 trunc v8i32 %in" we do:
1384   //   %inlo = v4i32 extract_subvector %in, 0
1385   //   %inhi = v4i32 extract_subvector %in, 4
1386   //   %lo16 = v4i16 trunc v4i32 %inlo
1387   //   %hi16 = v4i16 trunc v4i32 %inhi
1388   //   %in16 = v8i16 concat_vectors v4i16 %lo16, v4i16 %hi16
1389   //   %res = v8i8 trunc v8i16 %in16
1390   //
1391   // Without this transform, the original truncate would end up being
1392   // scalarized, which is pretty much always a last resort.
1393   SDValue InVec = N->getOperand(0);
1394   EVT InVT = InVec->getValueType(0);
1395   EVT OutVT = N->getValueType(0);
1396   unsigned NumElements = OutVT.getVectorNumElements();
1397   // Widening should have already made sure this is a power-two vector
1398   // if we're trying to split it at all. assert() that's true, just in case.
1399   assert(!(NumElements & 1) && "Splitting vector, but not in half!");
1400
1401   unsigned InElementSize = InVT.getVectorElementType().getSizeInBits();
1402   unsigned OutElementSize = OutVT.getVectorElementType().getSizeInBits();
1403
1404   // If the input elements are only 1/2 the width of the result elements,
1405   // just use the normal splitting. Our trick only work if there's room
1406   // to split more than once.
1407   if (InElementSize <= OutElementSize * 2)
1408     return SplitVecOp_UnaryOp(N);
1409   SDLoc DL(N);
1410
1411   // Extract the halves of the input via extract_subvector.
1412   EVT SplitVT = EVT::getVectorVT(*DAG.getContext(),
1413                                  InVT.getVectorElementType(), NumElements/2);
1414   SDValue InLoVec = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, InVec,
1415                                 DAG.getConstant(0, TLI.getVectorIdxTy()));
1416   SDValue InHiVec = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, InVec,
1417                                 DAG.getConstant(NumElements/2,
1418                                 TLI.getVectorIdxTy()));
1419   // Truncate them to 1/2 the element size.
1420   EVT HalfElementVT = EVT::getIntegerVT(*DAG.getContext(), InElementSize/2);
1421   EVT HalfVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT,
1422                                 NumElements/2);
1423   SDValue HalfLo = DAG.getNode(ISD::TRUNCATE, DL, HalfVT, InLoVec);
1424   SDValue HalfHi = DAG.getNode(ISD::TRUNCATE, DL, HalfVT, InHiVec);
1425   // Concatenate them to get the full intermediate truncation result.
1426   EVT InterVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT, NumElements);
1427   SDValue InterVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InterVT, HalfLo,
1428                                  HalfHi);
1429   // Now finish up by truncating all the way down to the original result
1430   // type. This should normally be something that ends up being legal directly,
1431   // but in theory if a target has very wide vectors and an annoyingly
1432   // restricted set of legal types, this split can chain to build things up.
1433   return DAG.getNode(ISD::TRUNCATE, DL, OutVT, InterVec);
1434 }
1435
1436 SDValue DAGTypeLegalizer::SplitVecOp_VSETCC(SDNode *N) {
1437   assert(N->getValueType(0).isVector() &&
1438          N->getOperand(0).getValueType().isVector() &&
1439          "Operand types must be vectors");
1440   // The result has a legal vector type, but the input needs splitting.
1441   SDValue Lo0, Hi0, Lo1, Hi1, LoRes, HiRes;
1442   SDLoc DL(N);
1443   GetSplitVector(N->getOperand(0), Lo0, Hi0);
1444   GetSplitVector(N->getOperand(1), Lo1, Hi1);
1445   unsigned PartElements = Lo0.getValueType().getVectorNumElements();
1446   EVT PartResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, PartElements);
1447   EVT WideResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, 2*PartElements);
1448
1449   LoRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Lo0, Lo1, N->getOperand(2));
1450   HiRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Hi0, Hi1, N->getOperand(2));
1451   SDValue Con = DAG.getNode(ISD::CONCAT_VECTORS, DL, WideResVT, LoRes, HiRes);
1452   return PromoteTargetBoolean(Con, N->getValueType(0));
1453 }
1454
1455
1456 SDValue DAGTypeLegalizer::SplitVecOp_FP_ROUND(SDNode *N) {
1457   // The result has a legal vector type, but the input needs splitting.
1458   EVT ResVT = N->getValueType(0);
1459   SDValue Lo, Hi;
1460   SDLoc DL(N);
1461   GetSplitVector(N->getOperand(0), Lo, Hi);
1462   EVT InVT = Lo.getValueType();
1463
1464   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
1465                                InVT.getVectorNumElements());
1466
1467   Lo = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Lo, N->getOperand(1));
1468   Hi = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Hi, N->getOperand(1));
1469
1470   return DAG.getNode(ISD::CONCAT_VECTORS, DL, ResVT, Lo, Hi);
1471 }
1472
1473
1474
1475 //===----------------------------------------------------------------------===//
1476 //  Result Vector Widening
1477 //===----------------------------------------------------------------------===//
1478
1479 void DAGTypeLegalizer::WidenVectorResult(SDNode *N, unsigned ResNo) {
1480   DEBUG(dbgs() << "Widen node result " << ResNo << ": ";
1481         N->dump(&DAG);
1482         dbgs() << "\n");
1483
1484   // See if the target wants to custom widen this node.
1485   if (CustomWidenLowerNode(N, N->getValueType(ResNo)))
1486     return;
1487
1488   SDValue Res = SDValue();
1489   switch (N->getOpcode()) {
1490   default:
1491 #ifndef NDEBUG
1492     dbgs() << "WidenVectorResult #" << ResNo << ": ";
1493     N->dump(&DAG);
1494     dbgs() << "\n";
1495 #endif
1496     llvm_unreachable("Do not know how to widen the result of this operator!");
1497
1498   case ISD::MERGE_VALUES:      Res = WidenVecRes_MERGE_VALUES(N, ResNo); break;
1499   case ISD::BITCAST:           Res = WidenVecRes_BITCAST(N); break;
1500   case ISD::BUILD_VECTOR:      Res = WidenVecRes_BUILD_VECTOR(N); break;
1501   case ISD::CONCAT_VECTORS:    Res = WidenVecRes_CONCAT_VECTORS(N); break;
1502   case ISD::CONVERT_RNDSAT:    Res = WidenVecRes_CONVERT_RNDSAT(N); break;
1503   case ISD::EXTRACT_SUBVECTOR: Res = WidenVecRes_EXTRACT_SUBVECTOR(N); break;
1504   case ISD::FP_ROUND_INREG:    Res = WidenVecRes_InregOp(N); break;
1505   case ISD::INSERT_VECTOR_ELT: Res = WidenVecRes_INSERT_VECTOR_ELT(N); break;
1506   case ISD::LOAD:              Res = WidenVecRes_LOAD(N); break;
1507   case ISD::SCALAR_TO_VECTOR:  Res = WidenVecRes_SCALAR_TO_VECTOR(N); break;
1508   case ISD::SIGN_EXTEND_INREG: Res = WidenVecRes_InregOp(N); break;
1509   case ISD::VSELECT:
1510   case ISD::SELECT:            Res = WidenVecRes_SELECT(N); break;
1511   case ISD::SELECT_CC:         Res = WidenVecRes_SELECT_CC(N); break;
1512   case ISD::SETCC:             Res = WidenVecRes_SETCC(N); break;
1513   case ISD::UNDEF:             Res = WidenVecRes_UNDEF(N); break;
1514   case ISD::VECTOR_SHUFFLE:
1515     Res = WidenVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N));
1516     break;
1517
1518   case ISD::ADD:
1519   case ISD::AND:
1520   case ISD::BSWAP:
1521   case ISD::MUL:
1522   case ISD::MULHS:
1523   case ISD::MULHU:
1524   case ISD::OR:
1525   case ISD::SUB:
1526   case ISD::XOR:
1527     Res = WidenVecRes_Binary(N);
1528     break;
1529
1530   case ISD::FADD:
1531   case ISD::FCOPYSIGN:
1532   case ISD::FMUL:
1533   case ISD::FPOW:
1534   case ISD::FSUB:
1535   case ISD::FDIV:
1536   case ISD::FREM:
1537   case ISD::SDIV:
1538   case ISD::UDIV:
1539   case ISD::SREM:
1540   case ISD::UREM:
1541     Res = WidenVecRes_BinaryCanTrap(N);
1542     break;
1543
1544   case ISD::FPOWI:
1545     Res = WidenVecRes_POWI(N);
1546     break;
1547
1548   case ISD::SHL:
1549   case ISD::SRA:
1550   case ISD::SRL:
1551     Res = WidenVecRes_Shift(N);
1552     break;
1553
1554   case ISD::ANY_EXTEND:
1555   case ISD::FP_EXTEND:
1556   case ISD::FP_ROUND:
1557   case ISD::FP_TO_SINT:
1558   case ISD::FP_TO_UINT:
1559   case ISD::SIGN_EXTEND:
1560   case ISD::SINT_TO_FP:
1561   case ISD::TRUNCATE:
1562   case ISD::UINT_TO_FP:
1563   case ISD::ZERO_EXTEND:
1564     Res = WidenVecRes_Convert(N);
1565     break;
1566
1567   case ISD::CTLZ:
1568   case ISD::CTPOP:
1569   case ISD::CTTZ:
1570   case ISD::FABS:
1571   case ISD::FCEIL:
1572   case ISD::FCOS:
1573   case ISD::FEXP:
1574   case ISD::FEXP2:
1575   case ISD::FFLOOR:
1576   case ISD::FLOG:
1577   case ISD::FLOG10:
1578   case ISD::FLOG2:
1579   case ISD::FNEARBYINT:
1580   case ISD::FNEG:
1581   case ISD::FRINT:
1582   case ISD::FROUND:
1583   case ISD::FSIN:
1584   case ISD::FSQRT:
1585   case ISD::FTRUNC:
1586     Res = WidenVecRes_Unary(N);
1587     break;
1588   case ISD::FMA:
1589     Res = WidenVecRes_Ternary(N);
1590     break;
1591   }
1592
1593   // If Res is null, the sub-method took care of registering the result.
1594   if (Res.getNode())
1595     SetWidenedVector(SDValue(N, ResNo), Res);
1596 }
1597
1598 SDValue DAGTypeLegalizer::WidenVecRes_Ternary(SDNode *N) {
1599   // Ternary op widening.
1600   SDLoc dl(N);
1601   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1602   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1603   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1604   SDValue InOp3 = GetWidenedVector(N->getOperand(2));
1605   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, InOp3);
1606 }
1607
1608 SDValue DAGTypeLegalizer::WidenVecRes_Binary(SDNode *N) {
1609   // Binary op widening.
1610   SDLoc dl(N);
1611   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1612   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1613   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1614   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2);
1615 }
1616
1617 SDValue DAGTypeLegalizer::WidenVecRes_BinaryCanTrap(SDNode *N) {
1618   // Binary op widening for operations that can trap.
1619   unsigned Opcode = N->getOpcode();
1620   SDLoc dl(N);
1621   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1622   EVT WidenEltVT = WidenVT.getVectorElementType();
1623   EVT VT = WidenVT;
1624   unsigned NumElts =  VT.getVectorNumElements();
1625   while (!TLI.isTypeLegal(VT) && NumElts != 1) {
1626     NumElts = NumElts / 2;
1627     VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
1628   }
1629
1630   if (NumElts != 1 && !TLI.canOpTrap(N->getOpcode(), VT)) {
1631     // Operation doesn't trap so just widen as normal.
1632     SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1633     SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1634     return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2);
1635   }
1636
1637   // No legal vector version so unroll the vector operation and then widen.
1638   if (NumElts == 1)
1639     return DAG.UnrollVectorOp(N, WidenVT.getVectorNumElements());
1640
1641   // Since the operation can trap, apply operation on the original vector.
1642   EVT MaxVT = VT;
1643   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
1644   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
1645   unsigned CurNumElts = N->getValueType(0).getVectorNumElements();
1646
1647   SmallVector<SDValue, 16> ConcatOps(CurNumElts);
1648   unsigned ConcatEnd = 0;  // Current ConcatOps index.
1649   int Idx = 0;        // Current Idx into input vectors.
1650
1651   // NumElts := greatest legal vector size (at most WidenVT)
1652   // while (orig. vector has unhandled elements) {
1653   //   take munches of size NumElts from the beginning and add to ConcatOps
1654   //   NumElts := next smaller supported vector size or 1
1655   // }
1656   while (CurNumElts != 0) {
1657     while (CurNumElts >= NumElts) {
1658       SDValue EOp1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, InOp1,
1659                                  DAG.getConstant(Idx, TLI.getVectorIdxTy()));
1660       SDValue EOp2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, InOp2,
1661                                  DAG.getConstant(Idx, TLI.getVectorIdxTy()));
1662       ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, VT, EOp1, EOp2);
1663       Idx += NumElts;
1664       CurNumElts -= NumElts;
1665     }
1666     do {
1667       NumElts = NumElts / 2;
1668       VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
1669     } while (!TLI.isTypeLegal(VT) && NumElts != 1);
1670
1671     if (NumElts == 1) {
1672       for (unsigned i = 0; i != CurNumElts; ++i, ++Idx) {
1673         SDValue EOp1 = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT,
1674                                    InOp1, DAG.getConstant(Idx,
1675                                                          TLI.getVectorIdxTy()));
1676         SDValue EOp2 = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT,
1677                                    InOp2, DAG.getConstant(Idx,
1678                                                          TLI.getVectorIdxTy()));
1679         ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, WidenEltVT,
1680                                              EOp1, EOp2);
1681       }
1682       CurNumElts = 0;
1683     }
1684   }
1685
1686   // Check to see if we have a single operation with the widen type.
1687   if (ConcatEnd == 1) {
1688     VT = ConcatOps[0].getValueType();
1689     if (VT == WidenVT)
1690       return ConcatOps[0];
1691   }
1692
1693   // while (Some element of ConcatOps is not of type MaxVT) {
1694   //   From the end of ConcatOps, collect elements of the same type and put
1695   //   them into an op of the next larger supported type
1696   // }
1697   while (ConcatOps[ConcatEnd-1].getValueType() != MaxVT) {
1698     Idx = ConcatEnd - 1;
1699     VT = ConcatOps[Idx--].getValueType();
1700     while (Idx >= 0 && ConcatOps[Idx].getValueType() == VT)
1701       Idx--;
1702
1703     int NextSize = VT.isVector() ? VT.getVectorNumElements() : 1;
1704     EVT NextVT;
1705     do {
1706       NextSize *= 2;
1707       NextVT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NextSize);
1708     } while (!TLI.isTypeLegal(NextVT));
1709
1710     if (!VT.isVector()) {
1711       // Scalar type, create an INSERT_VECTOR_ELEMENT of type NextVT
1712       SDValue VecOp = DAG.getUNDEF(NextVT);
1713       unsigned NumToInsert = ConcatEnd - Idx - 1;
1714       for (unsigned i = 0, OpIdx = Idx+1; i < NumToInsert; i++, OpIdx++) {
1715         VecOp = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NextVT, VecOp,
1716                             ConcatOps[OpIdx], DAG.getConstant(i,
1717                                                          TLI.getVectorIdxTy()));
1718       }
1719       ConcatOps[Idx+1] = VecOp;
1720       ConcatEnd = Idx + 2;
1721     } else {
1722       // Vector type, create a CONCAT_VECTORS of type NextVT
1723       SDValue undefVec = DAG.getUNDEF(VT);
1724       unsigned OpsToConcat = NextSize/VT.getVectorNumElements();
1725       SmallVector<SDValue, 16> SubConcatOps(OpsToConcat);
1726       unsigned RealVals = ConcatEnd - Idx - 1;
1727       unsigned SubConcatEnd = 0;
1728       unsigned SubConcatIdx = Idx + 1;
1729       while (SubConcatEnd < RealVals)
1730         SubConcatOps[SubConcatEnd++] = ConcatOps[++Idx];
1731       while (SubConcatEnd < OpsToConcat)
1732         SubConcatOps[SubConcatEnd++] = undefVec;
1733       ConcatOps[SubConcatIdx] = DAG.getNode(ISD::CONCAT_VECTORS, dl,
1734                                             NextVT, &SubConcatOps[0],
1735                                             OpsToConcat);
1736       ConcatEnd = SubConcatIdx + 1;
1737     }
1738   }
1739
1740   // Check to see if we have a single operation with the widen type.
1741   if (ConcatEnd == 1) {
1742     VT = ConcatOps[0].getValueType();
1743     if (VT == WidenVT)
1744       return ConcatOps[0];
1745   }
1746
1747   // add undefs of size MaxVT until ConcatOps grows to length of WidenVT
1748   unsigned NumOps = WidenVT.getVectorNumElements()/MaxVT.getVectorNumElements();
1749   if (NumOps != ConcatEnd ) {
1750     SDValue UndefVal = DAG.getUNDEF(MaxVT);
1751     for (unsigned j = ConcatEnd; j < NumOps; ++j)
1752       ConcatOps[j] = UndefVal;
1753   }
1754   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &ConcatOps[0], NumOps);
1755 }
1756
1757 SDValue DAGTypeLegalizer::WidenVecRes_Convert(SDNode *N) {
1758   SDValue InOp = N->getOperand(0);
1759   SDLoc DL(N);
1760
1761   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1762   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1763
1764   EVT InVT = InOp.getValueType();
1765   EVT InEltVT = InVT.getVectorElementType();
1766   EVT InWidenVT = EVT::getVectorVT(*DAG.getContext(), InEltVT, WidenNumElts);
1767
1768   unsigned Opcode = N->getOpcode();
1769   unsigned InVTNumElts = InVT.getVectorNumElements();
1770
1771   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
1772     InOp = GetWidenedVector(N->getOperand(0));
1773     InVT = InOp.getValueType();
1774     InVTNumElts = InVT.getVectorNumElements();
1775     if (InVTNumElts == WidenNumElts) {
1776       if (N->getNumOperands() == 1)
1777         return DAG.getNode(Opcode, DL, WidenVT, InOp);
1778       return DAG.getNode(Opcode, DL, WidenVT, InOp, N->getOperand(1));
1779     }
1780   }
1781
1782   if (TLI.isTypeLegal(InWidenVT)) {
1783     // Because the result and the input are different vector types, widening
1784     // the result could create a legal type but widening the input might make
1785     // it an illegal type that might lead to repeatedly splitting the input
1786     // and then widening it. To avoid this, we widen the input only if
1787     // it results in a legal type.
1788     if (WidenNumElts % InVTNumElts == 0) {
1789       // Widen the input and call convert on the widened input vector.
1790       unsigned NumConcat = WidenNumElts/InVTNumElts;
1791       SmallVector<SDValue, 16> Ops(NumConcat);
1792       Ops[0] = InOp;
1793       SDValue UndefVal = DAG.getUNDEF(InVT);
1794       for (unsigned i = 1; i != NumConcat; ++i)
1795         Ops[i] = UndefVal;
1796       SDValue InVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InWidenVT,
1797                                   &Ops[0], NumConcat);
1798       if (N->getNumOperands() == 1)
1799         return DAG.getNode(Opcode, DL, WidenVT, InVec);
1800       return DAG.getNode(Opcode, DL, WidenVT, InVec, N->getOperand(1));
1801     }
1802
1803     if (InVTNumElts % WidenNumElts == 0) {
1804       SDValue InVal = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, InWidenVT,
1805                                   InOp, DAG.getConstant(0,
1806                                                         TLI.getVectorIdxTy()));
1807       // Extract the input and convert the shorten input vector.
1808       if (N->getNumOperands() == 1)
1809         return DAG.getNode(Opcode, DL, WidenVT, InVal);
1810       return DAG.getNode(Opcode, DL, WidenVT, InVal, N->getOperand(1));
1811     }
1812   }
1813
1814   // Otherwise unroll into some nasty scalar code and rebuild the vector.
1815   SmallVector<SDValue, 16> Ops(WidenNumElts);
1816   EVT EltVT = WidenVT.getVectorElementType();
1817   unsigned MinElts = std::min(InVTNumElts, WidenNumElts);
1818   unsigned i;
1819   for (i=0; i < MinElts; ++i) {
1820     SDValue Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, InEltVT, InOp,
1821                               DAG.getConstant(i, TLI.getVectorIdxTy()));
1822     if (N->getNumOperands() == 1)
1823       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val);
1824     else
1825       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val, N->getOperand(1));
1826   }
1827
1828   SDValue UndefVal = DAG.getUNDEF(EltVT);
1829   for (; i < WidenNumElts; ++i)
1830     Ops[i] = UndefVal;
1831
1832   return DAG.getNode(ISD::BUILD_VECTOR, DL, WidenVT, &Ops[0], WidenNumElts);
1833 }
1834
1835 SDValue DAGTypeLegalizer::WidenVecRes_POWI(SDNode *N) {
1836   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1837   SDValue InOp = GetWidenedVector(N->getOperand(0));
1838   SDValue ShOp = N->getOperand(1);
1839   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
1840 }
1841
1842 SDValue DAGTypeLegalizer::WidenVecRes_Shift(SDNode *N) {
1843   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1844   SDValue InOp = GetWidenedVector(N->getOperand(0));
1845   SDValue ShOp = N->getOperand(1);
1846
1847   EVT ShVT = ShOp.getValueType();
1848   if (getTypeAction(ShVT) == TargetLowering::TypeWidenVector) {
1849     ShOp = GetWidenedVector(ShOp);
1850     ShVT = ShOp.getValueType();
1851   }
1852   EVT ShWidenVT = EVT::getVectorVT(*DAG.getContext(),
1853                                    ShVT.getVectorElementType(),
1854                                    WidenVT.getVectorNumElements());
1855   if (ShVT != ShWidenVT)
1856     ShOp = ModifyToType(ShOp, ShWidenVT);
1857
1858   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
1859 }
1860
1861 SDValue DAGTypeLegalizer::WidenVecRes_Unary(SDNode *N) {
1862   // Unary op widening.
1863   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1864   SDValue InOp = GetWidenedVector(N->getOperand(0));
1865   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp);
1866 }
1867
1868 SDValue DAGTypeLegalizer::WidenVecRes_InregOp(SDNode *N) {
1869   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1870   EVT ExtVT = EVT::getVectorVT(*DAG.getContext(),
1871                                cast<VTSDNode>(N->getOperand(1))->getVT()
1872                                  .getVectorElementType(),
1873                                WidenVT.getVectorNumElements());
1874   SDValue WidenLHS = GetWidenedVector(N->getOperand(0));
1875   return DAG.getNode(N->getOpcode(), SDLoc(N),
1876                      WidenVT, WidenLHS, DAG.getValueType(ExtVT));
1877 }
1878
1879 SDValue DAGTypeLegalizer::WidenVecRes_MERGE_VALUES(SDNode *N, unsigned ResNo) {
1880   SDValue WidenVec = DisintegrateMERGE_VALUES(N, ResNo);
1881   return GetWidenedVector(WidenVec);
1882 }
1883
1884 SDValue DAGTypeLegalizer::WidenVecRes_BITCAST(SDNode *N) {
1885   SDValue InOp = N->getOperand(0);
1886   EVT InVT = InOp.getValueType();
1887   EVT VT = N->getValueType(0);
1888   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
1889   SDLoc dl(N);
1890
1891   switch (getTypeAction(InVT)) {
1892   case TargetLowering::TypeLegal:
1893     break;
1894   case TargetLowering::TypePromoteInteger:
1895     // If the incoming type is a vector that is being promoted, then
1896     // we know that the elements are arranged differently and that we
1897     // must perform the conversion using a stack slot.
1898     if (InVT.isVector())
1899       break;
1900
1901     // If the InOp is promoted to the same size, convert it.  Otherwise,
1902     // fall out of the switch and widen the promoted input.
1903     InOp = GetPromotedInteger(InOp);
1904     InVT = InOp.getValueType();
1905     if (WidenVT.bitsEq(InVT))
1906       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
1907     break;
1908   case TargetLowering::TypeSoftenFloat:
1909   case TargetLowering::TypeExpandInteger:
1910   case TargetLowering::TypeExpandFloat:
1911   case TargetLowering::TypeScalarizeVector:
1912   case TargetLowering::TypeSplitVector:
1913     break;
1914   case TargetLowering::TypeWidenVector:
1915     // If the InOp is widened to the same size, convert it.  Otherwise, fall
1916     // out of the switch and widen the widened input.
1917     InOp = GetWidenedVector(InOp);
1918     InVT = InOp.getValueType();
1919     if (WidenVT.bitsEq(InVT))
1920       // The input widens to the same size. Convert to the widen value.
1921       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
1922     break;
1923   }
1924
1925   unsigned WidenSize = WidenVT.getSizeInBits();
1926   unsigned InSize = InVT.getSizeInBits();
1927   // x86mmx is not an acceptable vector element type, so don't try.
1928   if (WidenSize % InSize == 0 && InVT != MVT::x86mmx) {
1929     // Determine new input vector type.  The new input vector type will use
1930     // the same element type (if its a vector) or use the input type as a
1931     // vector.  It is the same size as the type to widen to.
1932     EVT NewInVT;
1933     unsigned NewNumElts = WidenSize / InSize;
1934     if (InVT.isVector()) {
1935       EVT InEltVT = InVT.getVectorElementType();
1936       NewInVT = EVT::getVectorVT(*DAG.getContext(), InEltVT,
1937                                  WidenSize / InEltVT.getSizeInBits());
1938     } else {
1939       NewInVT = EVT::getVectorVT(*DAG.getContext(), InVT, NewNumElts);
1940     }
1941
1942     if (TLI.isTypeLegal(NewInVT)) {
1943       // Because the result and the input are different vector types, widening
1944       // the result could create a legal type but widening the input might make
1945       // it an illegal type that might lead to repeatedly splitting the input
1946       // and then widening it. To avoid this, we widen the input only if
1947       // it results in a legal type.
1948       SmallVector<SDValue, 16> Ops(NewNumElts);
1949       SDValue UndefVal = DAG.getUNDEF(InVT);
1950       Ops[0] = InOp;
1951       for (unsigned i = 1; i < NewNumElts; ++i)
1952         Ops[i] = UndefVal;
1953
1954       SDValue NewVec;
1955       if (InVT.isVector())
1956         NewVec = DAG.getNode(ISD::CONCAT_VECTORS, dl,
1957                              NewInVT, &Ops[0], NewNumElts);
1958       else
1959         NewVec = DAG.getNode(ISD::BUILD_VECTOR, dl,
1960                              NewInVT, &Ops[0], NewNumElts);
1961       return DAG.getNode(ISD::BITCAST, dl, WidenVT, NewVec);
1962     }
1963   }
1964
1965   return CreateStackStoreLoad(InOp, WidenVT);
1966 }
1967
1968 SDValue DAGTypeLegalizer::WidenVecRes_BUILD_VECTOR(SDNode *N) {
1969   SDLoc dl(N);
1970   // Build a vector with undefined for the new nodes.
1971   EVT VT = N->getValueType(0);
1972
1973   // Integer BUILD_VECTOR operands may be larger than the node's vector element
1974   // type. The UNDEFs need to have the same type as the existing operands.
1975   EVT EltVT = N->getOperand(0).getValueType();
1976   unsigned NumElts = VT.getVectorNumElements();
1977
1978   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
1979   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1980
1981   SmallVector<SDValue, 16> NewOps(N->op_begin(), N->op_end());
1982   assert(WidenNumElts >= NumElts && "Shrinking vector instead of widening!");
1983   NewOps.append(WidenNumElts - NumElts, DAG.getUNDEF(EltVT));
1984
1985   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &NewOps[0], NewOps.size());
1986 }
1987
1988 SDValue DAGTypeLegalizer::WidenVecRes_CONCAT_VECTORS(SDNode *N) {
1989   EVT InVT = N->getOperand(0).getValueType();
1990   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1991   SDLoc dl(N);
1992   unsigned WidenNumElts = WidenVT.getVectorNumElements();
1993   unsigned NumInElts = InVT.getVectorNumElements();
1994   unsigned NumOperands = N->getNumOperands();
1995
1996   bool InputWidened = false; // Indicates we need to widen the input.
1997   if (getTypeAction(InVT) != TargetLowering::TypeWidenVector) {
1998     if (WidenVT.getVectorNumElements() % InVT.getVectorNumElements() == 0) {
1999       // Add undef vectors to widen to correct length.
2000       unsigned NumConcat = WidenVT.getVectorNumElements() /
2001                            InVT.getVectorNumElements();
2002       SDValue UndefVal = DAG.getUNDEF(InVT);
2003       SmallVector<SDValue, 16> Ops(NumConcat);
2004       for (unsigned i=0; i < NumOperands; ++i)
2005         Ops[i] = N->getOperand(i);
2006       for (unsigned i = NumOperands; i != NumConcat; ++i)
2007         Ops[i] = UndefVal;
2008       return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &Ops[0], NumConcat);
2009     }
2010   } else {
2011     InputWidened = true;
2012     if (WidenVT == TLI.getTypeToTransformTo(*DAG.getContext(), InVT)) {
2013       // The inputs and the result are widen to the same value.
2014       unsigned i;
2015       for (i=1; i < NumOperands; ++i)
2016         if (N->getOperand(i).getOpcode() != ISD::UNDEF)
2017           break;
2018
2019       if (i == NumOperands)
2020         // Everything but the first operand is an UNDEF so just return the
2021         // widened first operand.
2022         return GetWidenedVector(N->getOperand(0));
2023
2024       if (NumOperands == 2) {
2025         // Replace concat of two operands with a shuffle.
2026         SmallVector<int, 16> MaskOps(WidenNumElts, -1);
2027         for (unsigned i = 0; i < NumInElts; ++i) {
2028           MaskOps[i] = i;
2029           MaskOps[i + NumInElts] = i + WidenNumElts;
2030         }
2031         return DAG.getVectorShuffle(WidenVT, dl,
2032                                     GetWidenedVector(N->getOperand(0)),
2033                                     GetWidenedVector(N->getOperand(1)),
2034                                     &MaskOps[0]);
2035       }
2036     }
2037   }
2038
2039   // Fall back to use extracts and build vector.
2040   EVT EltVT = WidenVT.getVectorElementType();
2041   SmallVector<SDValue, 16> Ops(WidenNumElts);
2042   unsigned Idx = 0;
2043   for (unsigned i=0; i < NumOperands; ++i) {
2044     SDValue InOp = N->getOperand(i);
2045     if (InputWidened)
2046       InOp = GetWidenedVector(InOp);
2047     for (unsigned j=0; j < NumInElts; ++j)
2048       Ops[Idx++] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2049                                DAG.getConstant(j, TLI.getVectorIdxTy()));
2050   }
2051   SDValue UndefVal = DAG.getUNDEF(EltVT);
2052   for (; Idx < WidenNumElts; ++Idx)
2053     Ops[Idx] = UndefVal;
2054   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], WidenNumElts);
2055 }
2056
2057 SDValue DAGTypeLegalizer::WidenVecRes_CONVERT_RNDSAT(SDNode *N) {
2058   SDLoc dl(N);
2059   SDValue InOp  = N->getOperand(0);
2060   SDValue RndOp = N->getOperand(3);
2061   SDValue SatOp = N->getOperand(4);
2062
2063   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2064   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2065
2066   EVT InVT = InOp.getValueType();
2067   EVT InEltVT = InVT.getVectorElementType();
2068   EVT InWidenVT = EVT::getVectorVT(*DAG.getContext(), InEltVT, WidenNumElts);
2069
2070   SDValue DTyOp = DAG.getValueType(WidenVT);
2071   SDValue STyOp = DAG.getValueType(InWidenVT);
2072   ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
2073
2074   unsigned InVTNumElts = InVT.getVectorNumElements();
2075   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
2076     InOp = GetWidenedVector(InOp);
2077     InVT = InOp.getValueType();
2078     InVTNumElts = InVT.getVectorNumElements();
2079     if (InVTNumElts == WidenNumElts)
2080       return DAG.getConvertRndSat(WidenVT, dl, InOp, DTyOp, STyOp, RndOp,
2081                                   SatOp, CvtCode);
2082   }
2083
2084   if (TLI.isTypeLegal(InWidenVT)) {
2085     // Because the result and the input are different vector types, widening
2086     // the result could create a legal type but widening the input might make
2087     // it an illegal type that might lead to repeatedly splitting the input
2088     // and then widening it. To avoid this, we widen the input only if
2089     // it results in a legal type.
2090     if (WidenNumElts % InVTNumElts == 0) {
2091       // Widen the input and call convert on the widened input vector.
2092       unsigned NumConcat = WidenNumElts/InVTNumElts;
2093       SmallVector<SDValue, 16> Ops(NumConcat);
2094       Ops[0] = InOp;
2095       SDValue UndefVal = DAG.getUNDEF(InVT);
2096       for (unsigned i = 1; i != NumConcat; ++i)
2097         Ops[i] = UndefVal;
2098
2099       InOp = DAG.getNode(ISD::CONCAT_VECTORS, dl, InWidenVT, &Ops[0],NumConcat);
2100       return DAG.getConvertRndSat(WidenVT, dl, InOp, DTyOp, STyOp, RndOp,
2101                                   SatOp, CvtCode);
2102     }
2103
2104     if (InVTNumElts % WidenNumElts == 0) {
2105       // Extract the input and convert the shorten input vector.
2106       InOp = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, InWidenVT, InOp,
2107                          DAG.getConstant(0, TLI.getVectorIdxTy()));
2108       return DAG.getConvertRndSat(WidenVT, dl, InOp, DTyOp, STyOp, RndOp,
2109                                   SatOp, CvtCode);
2110     }
2111   }
2112
2113   // Otherwise unroll into some nasty scalar code and rebuild the vector.
2114   SmallVector<SDValue, 16> Ops(WidenNumElts);
2115   EVT EltVT = WidenVT.getVectorElementType();
2116   DTyOp = DAG.getValueType(EltVT);
2117   STyOp = DAG.getValueType(InEltVT);
2118
2119   unsigned MinElts = std::min(InVTNumElts, WidenNumElts);
2120   unsigned i;
2121   for (i=0; i < MinElts; ++i) {
2122     SDValue ExtVal = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
2123                                  DAG.getConstant(i, TLI.getVectorIdxTy()));
2124     Ops[i] = DAG.getConvertRndSat(WidenVT, dl, ExtVal, DTyOp, STyOp, RndOp,
2125                                   SatOp, CvtCode);
2126   }
2127
2128   SDValue UndefVal = DAG.getUNDEF(EltVT);
2129   for (; i < WidenNumElts; ++i)
2130     Ops[i] = UndefVal;
2131
2132   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], WidenNumElts);
2133 }
2134
2135 SDValue DAGTypeLegalizer::WidenVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
2136   EVT      VT = N->getValueType(0);
2137   EVT      WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2138   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2139   SDValue  InOp = N->getOperand(0);
2140   SDValue  Idx  = N->getOperand(1);
2141   SDLoc dl(N);
2142
2143   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2144     InOp = GetWidenedVector(InOp);
2145
2146   EVT InVT = InOp.getValueType();
2147
2148   // Check if we can just return the input vector after widening.
2149   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
2150   if (IdxVal == 0 && InVT == WidenVT)
2151     return InOp;
2152
2153   // Check if we can extract from the vector.
2154   unsigned InNumElts = InVT.getVectorNumElements();
2155   if (IdxVal % WidenNumElts == 0 && IdxVal + WidenNumElts < InNumElts)
2156     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, WidenVT, InOp, Idx);
2157
2158   // We could try widening the input to the right length but for now, extract
2159   // the original elements, fill the rest with undefs and build a vector.
2160   SmallVector<SDValue, 16> Ops(WidenNumElts);
2161   EVT EltVT = VT.getVectorElementType();
2162   unsigned NumElts = VT.getVectorNumElements();
2163   unsigned i;
2164   for (i=0; i < NumElts; ++i)
2165     Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2166                          DAG.getConstant(IdxVal+i, TLI.getVectorIdxTy()));
2167
2168   SDValue UndefVal = DAG.getUNDEF(EltVT);
2169   for (; i < WidenNumElts; ++i)
2170     Ops[i] = UndefVal;
2171   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], WidenNumElts);
2172 }
2173
2174 SDValue DAGTypeLegalizer::WidenVecRes_INSERT_VECTOR_ELT(SDNode *N) {
2175   SDValue InOp = GetWidenedVector(N->getOperand(0));
2176   return DAG.getNode(ISD::INSERT_VECTOR_ELT, SDLoc(N),
2177                      InOp.getValueType(), InOp,
2178                      N->getOperand(1), N->getOperand(2));
2179 }
2180
2181 SDValue DAGTypeLegalizer::WidenVecRes_LOAD(SDNode *N) {
2182   LoadSDNode *LD = cast<LoadSDNode>(N);
2183   ISD::LoadExtType ExtType = LD->getExtensionType();
2184
2185   SDValue Result;
2186   SmallVector<SDValue, 16> LdChain;  // Chain for the series of load
2187   if (ExtType != ISD::NON_EXTLOAD)
2188     Result = GenWidenVectorExtLoads(LdChain, LD, ExtType);
2189   else
2190     Result = GenWidenVectorLoads(LdChain, LD);
2191
2192   // If we generate a single load, we can use that for the chain.  Otherwise,
2193   // build a factor node to remember the multiple loads are independent and
2194   // chain to that.
2195   SDValue NewChain;
2196   if (LdChain.size() == 1)
2197     NewChain = LdChain[0];
2198   else
2199     NewChain = DAG.getNode(ISD::TokenFactor, SDLoc(LD), MVT::Other,
2200                            &LdChain[0], LdChain.size());
2201
2202   // Modified the chain - switch anything that used the old chain to use
2203   // the new one.
2204   ReplaceValueWith(SDValue(N, 1), NewChain);
2205
2206   return Result;
2207 }
2208
2209 SDValue DAGTypeLegalizer::WidenVecRes_SCALAR_TO_VECTOR(SDNode *N) {
2210   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2211   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N),
2212                      WidenVT, N->getOperand(0));
2213 }
2214
2215 SDValue DAGTypeLegalizer::WidenVecRes_SELECT(SDNode *N) {
2216   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2217   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2218
2219   SDValue Cond1 = N->getOperand(0);
2220   EVT CondVT = Cond1.getValueType();
2221   if (CondVT.isVector()) {
2222     EVT CondEltVT = CondVT.getVectorElementType();
2223     EVT CondWidenVT =  EVT::getVectorVT(*DAG.getContext(),
2224                                         CondEltVT, WidenNumElts);
2225     if (getTypeAction(CondVT) == TargetLowering::TypeWidenVector)
2226       Cond1 = GetWidenedVector(Cond1);
2227
2228     if (Cond1.getValueType() != CondWidenVT)
2229       Cond1 = ModifyToType(Cond1, CondWidenVT);
2230   }
2231
2232   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
2233   SDValue InOp2 = GetWidenedVector(N->getOperand(2));
2234   assert(InOp1.getValueType() == WidenVT && InOp2.getValueType() == WidenVT);
2235   return DAG.getNode(N->getOpcode(), SDLoc(N),
2236                      WidenVT, Cond1, InOp1, InOp2);
2237 }
2238
2239 SDValue DAGTypeLegalizer::WidenVecRes_SELECT_CC(SDNode *N) {
2240   SDValue InOp1 = GetWidenedVector(N->getOperand(2));
2241   SDValue InOp2 = GetWidenedVector(N->getOperand(3));
2242   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
2243                      InOp1.getValueType(), N->getOperand(0),
2244                      N->getOperand(1), InOp1, InOp2, N->getOperand(4));
2245 }
2246
2247 SDValue DAGTypeLegalizer::WidenVecRes_SETCC(SDNode *N) {
2248   assert(N->getValueType(0).isVector() ==
2249          N->getOperand(0).getValueType().isVector() &&
2250          "Scalar/Vector type mismatch");
2251   if (N->getValueType(0).isVector()) return WidenVecRes_VSETCC(N);
2252
2253   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2254   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2255   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2256   return DAG.getNode(ISD::SETCC, SDLoc(N), WidenVT,
2257                      InOp1, InOp2, N->getOperand(2));
2258 }
2259
2260 SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) {
2261  EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2262  return DAG.getUNDEF(WidenVT);
2263 }
2264
2265 SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N) {
2266   EVT VT = N->getValueType(0);
2267   SDLoc dl(N);
2268
2269   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2270   unsigned NumElts = VT.getVectorNumElements();
2271   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2272
2273   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2274   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2275
2276   // Adjust mask based on new input vector length.
2277   SmallVector<int, 16> NewMask;
2278   for (unsigned i = 0; i != NumElts; ++i) {
2279     int Idx = N->getMaskElt(i);
2280     if (Idx < (int)NumElts)
2281       NewMask.push_back(Idx);
2282     else
2283       NewMask.push_back(Idx - NumElts + WidenNumElts);
2284   }
2285   for (unsigned i = NumElts; i != WidenNumElts; ++i)
2286     NewMask.push_back(-1);
2287   return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, &NewMask[0]);
2288 }
2289
2290 SDValue DAGTypeLegalizer::WidenVecRes_VSETCC(SDNode *N) {
2291   assert(N->getValueType(0).isVector() &&
2292          N->getOperand(0).getValueType().isVector() &&
2293          "Operands must be vectors");
2294   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2295   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2296
2297   SDValue InOp1 = N->getOperand(0);
2298   EVT InVT = InOp1.getValueType();
2299   assert(InVT.isVector() && "can not widen non vector type");
2300   EVT WidenInVT = EVT::getVectorVT(*DAG.getContext(),
2301                                    InVT.getVectorElementType(), WidenNumElts);
2302   InOp1 = GetWidenedVector(InOp1);
2303   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2304
2305   // Assume that the input and output will be widen appropriately.  If not,
2306   // we will have to unroll it at some point.
2307   assert(InOp1.getValueType() == WidenInVT &&
2308          InOp2.getValueType() == WidenInVT &&
2309          "Input not widened to expected type!");
2310   (void)WidenInVT;
2311   return DAG.getNode(ISD::SETCC, SDLoc(N),
2312                      WidenVT, InOp1, InOp2, N->getOperand(2));
2313 }
2314
2315
2316 //===----------------------------------------------------------------------===//
2317 // Widen Vector Operand
2318 //===----------------------------------------------------------------------===//
2319 bool DAGTypeLegalizer::WidenVectorOperand(SDNode *N, unsigned OpNo) {
2320   DEBUG(dbgs() << "Widen node operand " << OpNo << ": ";
2321         N->dump(&DAG);
2322         dbgs() << "\n");
2323   SDValue Res = SDValue();
2324
2325   // See if the target wants to custom widen this node.
2326   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
2327     return false;
2328
2329   switch (N->getOpcode()) {
2330   default:
2331 #ifndef NDEBUG
2332     dbgs() << "WidenVectorOperand op #" << OpNo << ": ";
2333     N->dump(&DAG);
2334     dbgs() << "\n";
2335 #endif
2336     llvm_unreachable("Do not know how to widen this operator's operand!");
2337
2338   case ISD::BITCAST:            Res = WidenVecOp_BITCAST(N); break;
2339   case ISD::CONCAT_VECTORS:     Res = WidenVecOp_CONCAT_VECTORS(N); break;
2340   case ISD::EXTRACT_SUBVECTOR:  Res = WidenVecOp_EXTRACT_SUBVECTOR(N); break;
2341   case ISD::EXTRACT_VECTOR_ELT: Res = WidenVecOp_EXTRACT_VECTOR_ELT(N); break;
2342   case ISD::STORE:              Res = WidenVecOp_STORE(N); break;
2343   case ISD::SETCC:              Res = WidenVecOp_SETCC(N); break;
2344
2345   case ISD::FP_EXTEND:
2346   case ISD::FP_TO_SINT:
2347   case ISD::FP_TO_UINT:
2348   case ISD::SINT_TO_FP:
2349   case ISD::UINT_TO_FP:
2350   case ISD::TRUNCATE:
2351   case ISD::SIGN_EXTEND:
2352   case ISD::ZERO_EXTEND:
2353   case ISD::ANY_EXTEND:
2354     Res = WidenVecOp_Convert(N);
2355     break;
2356   }
2357
2358   // If Res is null, the sub-method took care of registering the result.
2359   if (!Res.getNode()) return false;
2360
2361   // If the result is N, the sub-method updated N in place.  Tell the legalizer
2362   // core about this.
2363   if (Res.getNode() == N)
2364     return true;
2365
2366
2367   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
2368          "Invalid operand expansion");
2369
2370   ReplaceValueWith(SDValue(N, 0), Res);
2371   return false;
2372 }
2373
2374 SDValue DAGTypeLegalizer::WidenVecOp_Convert(SDNode *N) {
2375   // Since the result is legal and the input is illegal, it is unlikely
2376   // that we can fix the input to a legal type so unroll the convert
2377   // into some scalar code and create a nasty build vector.
2378   EVT VT = N->getValueType(0);
2379   EVT EltVT = VT.getVectorElementType();
2380   SDLoc dl(N);
2381   unsigned NumElts = VT.getVectorNumElements();
2382   SDValue InOp = N->getOperand(0);
2383   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2384     InOp = GetWidenedVector(InOp);
2385   EVT InVT = InOp.getValueType();
2386   EVT InEltVT = InVT.getVectorElementType();
2387
2388   unsigned Opcode = N->getOpcode();
2389   SmallVector<SDValue, 16> Ops(NumElts);
2390   for (unsigned i=0; i < NumElts; ++i)
2391     Ops[i] = DAG.getNode(Opcode, dl, EltVT,
2392                          DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
2393                                      DAG.getConstant(i, TLI.getVectorIdxTy())));
2394
2395   return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElts);
2396 }
2397
2398 SDValue DAGTypeLegalizer::WidenVecOp_BITCAST(SDNode *N) {
2399   EVT VT = N->getValueType(0);
2400   SDValue InOp = GetWidenedVector(N->getOperand(0));
2401   EVT InWidenVT = InOp.getValueType();
2402   SDLoc dl(N);
2403
2404   // Check if we can convert between two legal vector types and extract.
2405   unsigned InWidenSize = InWidenVT.getSizeInBits();
2406   unsigned Size = VT.getSizeInBits();
2407   // x86mmx is not an acceptable vector element type, so don't try.
2408   if (InWidenSize % Size == 0 && !VT.isVector() && VT != MVT::x86mmx) {
2409     unsigned NewNumElts = InWidenSize / Size;
2410     EVT NewVT = EVT::getVectorVT(*DAG.getContext(), VT, NewNumElts);
2411     if (TLI.isTypeLegal(NewVT)) {
2412       SDValue BitOp = DAG.getNode(ISD::BITCAST, dl, NewVT, InOp);
2413       return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, VT, BitOp,
2414                          DAG.getConstant(0, TLI.getVectorIdxTy()));
2415     }
2416   }
2417
2418   return CreateStackStoreLoad(InOp, VT);
2419 }
2420
2421 SDValue DAGTypeLegalizer::WidenVecOp_CONCAT_VECTORS(SDNode *N) {
2422   // If the input vector is not legal, it is likely that we will not find a
2423   // legal vector of the same size. Replace the concatenate vector with a
2424   // nasty build vector.
2425   EVT VT = N->getValueType(0);
2426   EVT EltVT = VT.getVectorElementType();
2427   SDLoc dl(N);
2428   unsigned NumElts = VT.getVectorNumElements();
2429   SmallVector<SDValue, 16> Ops(NumElts);
2430
2431   EVT InVT = N->getOperand(0).getValueType();
2432   unsigned NumInElts = InVT.getVectorNumElements();
2433
2434   unsigned Idx = 0;
2435   unsigned NumOperands = N->getNumOperands();
2436   for (unsigned i=0; i < NumOperands; ++i) {
2437     SDValue InOp = N->getOperand(i);
2438     if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2439       InOp = GetWidenedVector(InOp);
2440     for (unsigned j=0; j < NumInElts; ++j)
2441       Ops[Idx++] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2442                                DAG.getConstant(j, TLI.getVectorIdxTy()));
2443   }
2444   return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElts);
2445 }
2446
2447 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
2448   SDValue InOp = GetWidenedVector(N->getOperand(0));
2449   return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(N),
2450                      N->getValueType(0), InOp, N->getOperand(1));
2451 }
2452
2453 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
2454   SDValue InOp = GetWidenedVector(N->getOperand(0));
2455   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
2456                      N->getValueType(0), InOp, N->getOperand(1));
2457 }
2458
2459 SDValue DAGTypeLegalizer::WidenVecOp_STORE(SDNode *N) {
2460   // We have to widen the value but we want only to store the original
2461   // vector type.
2462   StoreSDNode *ST = cast<StoreSDNode>(N);
2463
2464   SmallVector<SDValue, 16> StChain;
2465   if (ST->isTruncatingStore())
2466     GenWidenVectorTruncStores(StChain, ST);
2467   else
2468     GenWidenVectorStores(StChain, ST);
2469
2470   if (StChain.size() == 1)
2471     return StChain[0];
2472   else
2473     return DAG.getNode(ISD::TokenFactor, SDLoc(ST),
2474                        MVT::Other,&StChain[0],StChain.size());
2475 }
2476
2477 SDValue DAGTypeLegalizer::WidenVecOp_SETCC(SDNode *N) {
2478   SDValue InOp0 = GetWidenedVector(N->getOperand(0));
2479   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
2480   SDLoc dl(N);
2481
2482   // WARNING: In this code we widen the compare instruction with garbage.
2483   // This garbage may contain denormal floats which may be slow. Is this a real
2484   // concern ? Should we zero the unused lanes if this is a float compare ?
2485
2486   // Get a new SETCC node to compare the newly widened operands.
2487   // Only some of the compared elements are legal.
2488   EVT SVT = TLI.getSetCCResultType(*DAG.getContext(), InOp0.getValueType());
2489   SDValue WideSETCC = DAG.getNode(ISD::SETCC, SDLoc(N),
2490                      SVT, InOp0, InOp1, N->getOperand(2));
2491
2492   // Extract the needed results from the result vector.
2493   EVT ResVT = EVT::getVectorVT(*DAG.getContext(),
2494                                SVT.getVectorElementType(),
2495                                N->getValueType(0).getVectorNumElements());
2496   SDValue CC = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl,
2497                            ResVT, WideSETCC, DAG.getConstant(0,
2498                                              TLI.getVectorIdxTy()));
2499
2500   return PromoteTargetBoolean(CC, N->getValueType(0));
2501 }
2502
2503
2504 //===----------------------------------------------------------------------===//
2505 // Vector Widening Utilities
2506 //===----------------------------------------------------------------------===//
2507
2508 // Utility function to find the type to chop up a widen vector for load/store
2509 //  TLI:       Target lowering used to determine legal types.
2510 //  Width:     Width left need to load/store.
2511 //  WidenVT:   The widen vector type to load to/store from
2512 //  Align:     If 0, don't allow use of a wider type
2513 //  WidenEx:   If Align is not 0, the amount additional we can load/store from.
2514
2515 static EVT FindMemType(SelectionDAG& DAG, const TargetLowering &TLI,
2516                        unsigned Width, EVT WidenVT,
2517                        unsigned Align = 0, unsigned WidenEx = 0) {
2518   EVT WidenEltVT = WidenVT.getVectorElementType();
2519   unsigned WidenWidth = WidenVT.getSizeInBits();
2520   unsigned WidenEltWidth = WidenEltVT.getSizeInBits();
2521   unsigned AlignInBits = Align*8;
2522
2523   // If we have one element to load/store, return it.
2524   EVT RetVT = WidenEltVT;
2525   if (Width == WidenEltWidth)
2526     return RetVT;
2527
2528   // See if there is larger legal integer than the element type to load/store
2529   unsigned VT;
2530   for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE;
2531        VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) {
2532     EVT MemVT((MVT::SimpleValueType) VT);
2533     unsigned MemVTWidth = MemVT.getSizeInBits();
2534     if (MemVT.getSizeInBits() <= WidenEltWidth)
2535       break;
2536     if (TLI.isTypeLegal(MemVT) && (WidenWidth % MemVTWidth) == 0 &&
2537         isPowerOf2_32(WidenWidth / MemVTWidth) &&
2538         (MemVTWidth <= Width ||
2539          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
2540       RetVT = MemVT;
2541       break;
2542     }
2543   }
2544
2545   // See if there is a larger vector type to load/store that has the same vector
2546   // element type and is evenly divisible with the WidenVT.
2547   for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE;
2548        VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) {
2549     EVT MemVT = (MVT::SimpleValueType) VT;
2550     unsigned MemVTWidth = MemVT.getSizeInBits();
2551     if (TLI.isTypeLegal(MemVT) && WidenEltVT == MemVT.getVectorElementType() &&
2552         (WidenWidth % MemVTWidth) == 0 &&
2553         isPowerOf2_32(WidenWidth / MemVTWidth) &&
2554         (MemVTWidth <= Width ||
2555          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
2556       if (RetVT.getSizeInBits() < MemVTWidth || MemVT == WidenVT)
2557         return MemVT;
2558     }
2559   }
2560
2561   return RetVT;
2562 }
2563
2564 // Builds a vector type from scalar loads
2565 //  VecTy: Resulting Vector type
2566 //  LDOps: Load operators to build a vector type
2567 //  [Start,End) the list of loads to use.
2568 static SDValue BuildVectorFromScalar(SelectionDAG& DAG, EVT VecTy,
2569                                      SmallVectorImpl<SDValue> &LdOps,
2570                                      unsigned Start, unsigned End) {
2571   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2572   SDLoc dl(LdOps[Start]);
2573   EVT LdTy = LdOps[Start].getValueType();
2574   unsigned Width = VecTy.getSizeInBits();
2575   unsigned NumElts = Width / LdTy.getSizeInBits();
2576   EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), LdTy, NumElts);
2577
2578   unsigned Idx = 1;
2579   SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT,LdOps[Start]);
2580
2581   for (unsigned i = Start + 1; i != End; ++i) {
2582     EVT NewLdTy = LdOps[i].getValueType();
2583     if (NewLdTy != LdTy) {
2584       NumElts = Width / NewLdTy.getSizeInBits();
2585       NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewLdTy, NumElts);
2586       VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, VecOp);
2587       // Readjust position and vector position based on new load type
2588       Idx = Idx * LdTy.getSizeInBits() / NewLdTy.getSizeInBits();
2589       LdTy = NewLdTy;
2590     }
2591     VecOp = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NewVecVT, VecOp, LdOps[i],
2592                         DAG.getConstant(Idx++, TLI.getVectorIdxTy()));
2593   }
2594   return DAG.getNode(ISD::BITCAST, dl, VecTy, VecOp);
2595 }
2596
2597 SDValue DAGTypeLegalizer::GenWidenVectorLoads(SmallVectorImpl<SDValue> &LdChain,
2598                                               LoadSDNode *LD) {
2599   // The strategy assumes that we can efficiently load powers of two widths.
2600   // The routines chops the vector into the largest vector loads with the same
2601   // element type or scalar loads and then recombines it to the widen vector
2602   // type.
2603   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
2604   unsigned WidenWidth = WidenVT.getSizeInBits();
2605   EVT LdVT    = LD->getMemoryVT();
2606   SDLoc dl(LD);
2607   assert(LdVT.isVector() && WidenVT.isVector());
2608   assert(LdVT.getVectorElementType() == WidenVT.getVectorElementType());
2609
2610   // Load information
2611   SDValue   Chain = LD->getChain();
2612   SDValue   BasePtr = LD->getBasePtr();
2613   unsigned  Align    = LD->getAlignment();
2614   bool      isVolatile = LD->isVolatile();
2615   bool      isNonTemporal = LD->isNonTemporal();
2616   bool      isInvariant = LD->isInvariant();
2617   const MDNode *TBAAInfo = LD->getTBAAInfo();
2618
2619   int LdWidth = LdVT.getSizeInBits();
2620   int WidthDiff = WidenWidth - LdWidth;          // Difference
2621   unsigned LdAlign = (isVolatile) ? 0 : Align; // Allow wider loads
2622
2623   // Find the vector type that can load from.
2624   EVT NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
2625   int NewVTWidth = NewVT.getSizeInBits();
2626   SDValue LdOp = DAG.getLoad(NewVT, dl, Chain, BasePtr, LD->getPointerInfo(),
2627                              isVolatile, isNonTemporal, isInvariant, Align,
2628                              TBAAInfo);
2629   LdChain.push_back(LdOp.getValue(1));
2630
2631   // Check if we can load the element with one instruction
2632   if (LdWidth <= NewVTWidth) {
2633     if (!NewVT.isVector()) {
2634       unsigned NumElts = WidenWidth / NewVTWidth;
2635       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
2636       SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT, LdOp);
2637       return DAG.getNode(ISD::BITCAST, dl, WidenVT, VecOp);
2638     }
2639     if (NewVT == WidenVT)
2640       return LdOp;
2641
2642     assert(WidenWidth % NewVTWidth == 0);
2643     unsigned NumConcat = WidenWidth / NewVTWidth;
2644     SmallVector<SDValue, 16> ConcatOps(NumConcat);
2645     SDValue UndefVal = DAG.getUNDEF(NewVT);
2646     ConcatOps[0] = LdOp;
2647     for (unsigned i = 1; i != NumConcat; ++i)
2648       ConcatOps[i] = UndefVal;
2649     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &ConcatOps[0],
2650                        NumConcat);
2651   }
2652
2653   // Load vector by using multiple loads from largest vector to scalar
2654   SmallVector<SDValue, 16> LdOps;
2655   LdOps.push_back(LdOp);
2656
2657   LdWidth -= NewVTWidth;
2658   unsigned Offset = 0;
2659
2660   while (LdWidth > 0) {
2661     unsigned Increment = NewVTWidth / 8;
2662     Offset += Increment;
2663     BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
2664                           DAG.getConstant(Increment, BasePtr.getValueType()));
2665
2666     SDValue L;
2667     if (LdWidth < NewVTWidth) {
2668       // Our current type we are using is too large, find a better size
2669       NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
2670       NewVTWidth = NewVT.getSizeInBits();
2671       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
2672                       LD->getPointerInfo().getWithOffset(Offset), isVolatile,
2673                       isNonTemporal, isInvariant, MinAlign(Align, Increment),
2674                       TBAAInfo);
2675       LdChain.push_back(L.getValue(1));
2676       if (L->getValueType(0).isVector()) {
2677         SmallVector<SDValue, 16> Loads;
2678         Loads.push_back(L);
2679         unsigned size = L->getValueSizeInBits(0);
2680         while (size < LdOp->getValueSizeInBits(0)) {
2681           Loads.push_back(DAG.getUNDEF(L->getValueType(0)));
2682           size += L->getValueSizeInBits(0);
2683         }
2684         L = DAG.getNode(ISD::CONCAT_VECTORS, dl, LdOp->getValueType(0),
2685                         &Loads[0], Loads.size());
2686       }
2687     } else {
2688       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
2689                       LD->getPointerInfo().getWithOffset(Offset), isVolatile,
2690                       isNonTemporal, isInvariant, MinAlign(Align, Increment),
2691                       TBAAInfo);
2692       LdChain.push_back(L.getValue(1));
2693     }
2694
2695     LdOps.push_back(L);
2696
2697
2698     LdWidth -= NewVTWidth;
2699   }
2700
2701   // Build the vector from the loads operations
2702   unsigned End = LdOps.size();
2703   if (!LdOps[0].getValueType().isVector())
2704     // All the loads are scalar loads.
2705     return BuildVectorFromScalar(DAG, WidenVT, LdOps, 0, End);
2706
2707   // If the load contains vectors, build the vector using concat vector.
2708   // All of the vectors used to loads are power of 2 and the scalars load
2709   // can be combined to make a power of 2 vector.
2710   SmallVector<SDValue, 16> ConcatOps(End);
2711   int i = End - 1;
2712   int Idx = End;
2713   EVT LdTy = LdOps[i].getValueType();
2714   // First combine the scalar loads to a vector
2715   if (!LdTy.isVector())  {
2716     for (--i; i >= 0; --i) {
2717       LdTy = LdOps[i].getValueType();
2718       if (LdTy.isVector())
2719         break;
2720     }
2721     ConcatOps[--Idx] = BuildVectorFromScalar(DAG, LdTy, LdOps, i+1, End);
2722   }
2723   ConcatOps[--Idx] = LdOps[i];
2724   for (--i; i >= 0; --i) {
2725     EVT NewLdTy = LdOps[i].getValueType();
2726     if (NewLdTy != LdTy) {
2727       // Create a larger vector
2728       ConcatOps[End-1] = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewLdTy,
2729                                      &ConcatOps[Idx], End - Idx);
2730       Idx = End - 1;
2731       LdTy = NewLdTy;
2732     }
2733     ConcatOps[--Idx] = LdOps[i];
2734   }
2735
2736   if (WidenWidth == LdTy.getSizeInBits()*(End - Idx))
2737     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
2738                        &ConcatOps[Idx], End - Idx);
2739
2740   // We need to fill the rest with undefs to build the vector
2741   unsigned NumOps = WidenWidth / LdTy.getSizeInBits();
2742   SmallVector<SDValue, 16> WidenOps(NumOps);
2743   SDValue UndefVal = DAG.getUNDEF(LdTy);
2744   {
2745     unsigned i = 0;
2746     for (; i != End-Idx; ++i)
2747       WidenOps[i] = ConcatOps[Idx+i];
2748     for (; i != NumOps; ++i)
2749       WidenOps[i] = UndefVal;
2750   }
2751   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, &WidenOps[0],NumOps);
2752 }
2753
2754 SDValue
2755 DAGTypeLegalizer::GenWidenVectorExtLoads(SmallVectorImpl<SDValue> &LdChain,
2756                                          LoadSDNode *LD,
2757                                          ISD::LoadExtType ExtType) {
2758   // For extension loads, it may not be more efficient to chop up the vector
2759   // and then extended it.  Instead, we unroll the load and build a new vector.
2760   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
2761   EVT LdVT    = LD->getMemoryVT();
2762   SDLoc dl(LD);
2763   assert(LdVT.isVector() && WidenVT.isVector());
2764
2765   // Load information
2766   SDValue   Chain = LD->getChain();
2767   SDValue   BasePtr = LD->getBasePtr();
2768   unsigned  Align    = LD->getAlignment();
2769   bool      isVolatile = LD->isVolatile();
2770   bool      isNonTemporal = LD->isNonTemporal();
2771   const MDNode *TBAAInfo = LD->getTBAAInfo();
2772
2773   EVT EltVT = WidenVT.getVectorElementType();
2774   EVT LdEltVT = LdVT.getVectorElementType();
2775   unsigned NumElts = LdVT.getVectorNumElements();
2776
2777   // Load each element and widen
2778   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2779   SmallVector<SDValue, 16> Ops(WidenNumElts);
2780   unsigned Increment = LdEltVT.getSizeInBits() / 8;
2781   Ops[0] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, BasePtr,
2782                           LD->getPointerInfo(),
2783                           LdEltVT, isVolatile, isNonTemporal, Align, TBAAInfo);
2784   LdChain.push_back(Ops[0].getValue(1));
2785   unsigned i = 0, Offset = Increment;
2786   for (i=1; i < NumElts; ++i, Offset += Increment) {
2787     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
2788                                      BasePtr,
2789                                      DAG.getConstant(Offset,
2790                                                      BasePtr.getValueType()));
2791     Ops[i] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, NewBasePtr,
2792                             LD->getPointerInfo().getWithOffset(Offset), LdEltVT,
2793                             isVolatile, isNonTemporal, Align, TBAAInfo);
2794     LdChain.push_back(Ops[i].getValue(1));
2795   }
2796
2797   // Fill the rest with undefs
2798   SDValue UndefVal = DAG.getUNDEF(EltVT);
2799   for (; i != WidenNumElts; ++i)
2800     Ops[i] = UndefVal;
2801
2802   return DAG.getNode(ISD::BUILD_VECTOR, dl, WidenVT, &Ops[0], Ops.size());
2803 }
2804
2805
2806 void DAGTypeLegalizer::GenWidenVectorStores(SmallVectorImpl<SDValue> &StChain,
2807                                             StoreSDNode *ST) {
2808   // The strategy assumes that we can efficiently store powers of two widths.
2809   // The routines chops the vector into the largest vector stores with the same
2810   // element type or scalar stores.
2811   SDValue  Chain = ST->getChain();
2812   SDValue  BasePtr = ST->getBasePtr();
2813   unsigned Align = ST->getAlignment();
2814   bool     isVolatile = ST->isVolatile();
2815   bool     isNonTemporal = ST->isNonTemporal();
2816   const MDNode *TBAAInfo = ST->getTBAAInfo();
2817   SDValue  ValOp = GetWidenedVector(ST->getValue());
2818   SDLoc dl(ST);
2819
2820   EVT StVT = ST->getMemoryVT();
2821   unsigned StWidth = StVT.getSizeInBits();
2822   EVT ValVT = ValOp.getValueType();
2823   unsigned ValWidth = ValVT.getSizeInBits();
2824   EVT ValEltVT = ValVT.getVectorElementType();
2825   unsigned ValEltWidth = ValEltVT.getSizeInBits();
2826   assert(StVT.getVectorElementType() == ValEltVT);
2827
2828   int Idx = 0;          // current index to store
2829   unsigned Offset = 0;  // offset from base to store
2830   while (StWidth != 0) {
2831     // Find the largest vector type we can store with
2832     EVT NewVT = FindMemType(DAG, TLI, StWidth, ValVT);
2833     unsigned NewVTWidth = NewVT.getSizeInBits();
2834     unsigned Increment = NewVTWidth / 8;
2835     if (NewVT.isVector()) {
2836       unsigned NumVTElts = NewVT.getVectorNumElements();
2837       do {
2838         SDValue EOp = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, NewVT, ValOp,
2839                                    DAG.getConstant(Idx, TLI.getVectorIdxTy()));
2840         StChain.push_back(DAG.getStore(Chain, dl, EOp, BasePtr,
2841                                     ST->getPointerInfo().getWithOffset(Offset),
2842                                        isVolatile, isNonTemporal,
2843                                        MinAlign(Align, Offset), TBAAInfo));
2844         StWidth -= NewVTWidth;
2845         Offset += Increment;
2846         Idx += NumVTElts;
2847         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
2848                               DAG.getConstant(Increment, BasePtr.getValueType()));
2849       } while (StWidth != 0 && StWidth >= NewVTWidth);
2850     } else {
2851       // Cast the vector to the scalar type we can store
2852       unsigned NumElts = ValWidth / NewVTWidth;
2853       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
2854       SDValue VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, ValOp);
2855       // Readjust index position based on new vector type
2856       Idx = Idx * ValEltWidth / NewVTWidth;
2857       do {
2858         SDValue EOp = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, NewVT, VecOp,
2859                       DAG.getConstant(Idx++, TLI.getVectorIdxTy()));
2860         StChain.push_back(DAG.getStore(Chain, dl, EOp, BasePtr,
2861                                     ST->getPointerInfo().getWithOffset(Offset),
2862                                        isVolatile, isNonTemporal,
2863                                        MinAlign(Align, Offset), TBAAInfo));
2864         StWidth -= NewVTWidth;
2865         Offset += Increment;
2866         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
2867                             DAG.getConstant(Increment, BasePtr.getValueType()));
2868       } while (StWidth != 0 && StWidth >= NewVTWidth);
2869       // Restore index back to be relative to the original widen element type
2870       Idx = Idx * NewVTWidth / ValEltWidth;
2871     }
2872   }
2873 }
2874
2875 void
2876 DAGTypeLegalizer::GenWidenVectorTruncStores(SmallVectorImpl<SDValue> &StChain,
2877                                             StoreSDNode *ST) {
2878   // For extension loads, it may not be more efficient to truncate the vector
2879   // and then store it.  Instead, we extract each element and then store it.
2880   SDValue  Chain = ST->getChain();
2881   SDValue  BasePtr = ST->getBasePtr();
2882   unsigned Align = ST->getAlignment();
2883   bool     isVolatile = ST->isVolatile();
2884   bool     isNonTemporal = ST->isNonTemporal();
2885   const MDNode *TBAAInfo = ST->getTBAAInfo();
2886   SDValue  ValOp = GetWidenedVector(ST->getValue());
2887   SDLoc dl(ST);
2888
2889   EVT StVT = ST->getMemoryVT();
2890   EVT ValVT = ValOp.getValueType();
2891
2892   // It must be true that we the widen vector type is bigger than where
2893   // we need to store.
2894   assert(StVT.isVector() && ValOp.getValueType().isVector());
2895   assert(StVT.bitsLT(ValOp.getValueType()));
2896
2897   // For truncating stores, we can not play the tricks of chopping legal
2898   // vector types and bit cast it to the right type.  Instead, we unroll
2899   // the store.
2900   EVT StEltVT  = StVT.getVectorElementType();
2901   EVT ValEltVT = ValVT.getVectorElementType();
2902   unsigned Increment = ValEltVT.getSizeInBits() / 8;
2903   unsigned NumElts = StVT.getVectorNumElements();
2904   SDValue EOp = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
2905                             DAG.getConstant(0, TLI.getVectorIdxTy()));
2906   StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, BasePtr,
2907                                       ST->getPointerInfo(), StEltVT,
2908                                       isVolatile, isNonTemporal, Align,
2909                                       TBAAInfo));
2910   unsigned Offset = Increment;
2911   for (unsigned i=1; i < NumElts; ++i, Offset += Increment) {
2912     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
2913                                      BasePtr, DAG.getConstant(Offset,
2914                                                        BasePtr.getValueType()));
2915     SDValue EOp = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
2916                             DAG.getConstant(0, TLI.getVectorIdxTy()));
2917     StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, NewBasePtr,
2918                                       ST->getPointerInfo().getWithOffset(Offset),
2919                                         StEltVT, isVolatile, isNonTemporal,
2920                                         MinAlign(Align, Offset), TBAAInfo));
2921   }
2922 }
2923
2924 /// Modifies a vector input (widen or narrows) to a vector of NVT.  The
2925 /// input vector must have the same element type as NVT.
2926 SDValue DAGTypeLegalizer::ModifyToType(SDValue InOp, EVT NVT) {
2927   // Note that InOp might have been widened so it might already have
2928   // the right width or it might need be narrowed.
2929   EVT InVT = InOp.getValueType();
2930   assert(InVT.getVectorElementType() == NVT.getVectorElementType() &&
2931          "input and widen element type must match");
2932   SDLoc dl(InOp);
2933
2934   // Check if InOp already has the right width.
2935   if (InVT == NVT)
2936     return InOp;
2937
2938   unsigned InNumElts = InVT.getVectorNumElements();
2939   unsigned WidenNumElts = NVT.getVectorNumElements();
2940   if (WidenNumElts > InNumElts && WidenNumElts % InNumElts == 0) {
2941     unsigned NumConcat = WidenNumElts / InNumElts;
2942     SmallVector<SDValue, 16> Ops(NumConcat);
2943     SDValue UndefVal = DAG.getUNDEF(InVT);
2944     Ops[0] = InOp;
2945     for (unsigned i = 1; i != NumConcat; ++i)
2946       Ops[i] = UndefVal;
2947
2948     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, &Ops[0], NumConcat);
2949   }
2950
2951   if (WidenNumElts < InNumElts && InNumElts % WidenNumElts)
2952     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, NVT, InOp,
2953                        DAG.getConstant(0, TLI.getVectorIdxTy()));
2954
2955   // Fall back to extract and build.
2956   SmallVector<SDValue, 16> Ops(WidenNumElts);
2957   EVT EltVT = NVT.getVectorElementType();
2958   unsigned MinNumElts = std::min(WidenNumElts, InNumElts);
2959   unsigned Idx;
2960   for (Idx = 0; Idx < MinNumElts; ++Idx)
2961     Ops[Idx] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2962                            DAG.getConstant(Idx, TLI.getVectorIdxTy()));
2963
2964   SDValue UndefVal = DAG.getUNDEF(EltVT);
2965   for ( ; Idx < WidenNumElts; ++Idx)
2966     Ops[Idx] = UndefVal;
2967   return DAG.getNode(ISD::BUILD_VECTOR, dl, NVT, &Ops[0], WidenNumElts);
2968 }