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