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