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