lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

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