]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
MFV r323917: 8648 Fix range locking in ZIL commit codepath
[FreeBSD/FreeBSD.git] / contrib / llvm / lib / CodeGen / SelectionDAG / LegalizeVectorTypes.cpp
1 //===------- LegalizeVectorTypes.cpp - Legalization of vector types -------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file performs vector type splitting and scalarization for LegalizeTypes.
11 // Scalarization is the act of changing a computation in an illegal one-element
12 // vector type to be a computation in its scalar element type.  For example,
13 // implementing <1 x f32> arithmetic in a scalar f32 register.  This is needed
14 // as a base case when scalarizing vector arithmetic like <4 x f32>, which
15 // eventually decomposes to scalars if the target doesn't support v4f32 or v2f32
16 // types.
17 // Splitting is the act of changing a computation in an invalid vector type to
18 // be a computation in two vectors of half the size.  For example, implementing
19 // <128 x f32> operations in terms of two <64 x f32> operations.
20 //
21 //===----------------------------------------------------------------------===//
22
23 #include "LegalizeTypes.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/Support/ErrorHandling.h"
26 #include "llvm/Support/raw_ostream.h"
27 using namespace llvm;
28
29 #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::EXTRACT_SUBVECTOR: R = ScalarizeVecRes_EXTRACT_SUBVECTOR(N); break;
55   case ISD::FP_ROUND:          R = ScalarizeVecRes_FP_ROUND(N); break;
56   case ISD::FP_ROUND_INREG:    R = ScalarizeVecRes_InregOp(N); break;
57   case ISD::FPOWI:             R = ScalarizeVecRes_FPOWI(N); break;
58   case ISD::INSERT_VECTOR_ELT: R = ScalarizeVecRes_INSERT_VECTOR_ELT(N); break;
59   case ISD::LOAD:           R = ScalarizeVecRes_LOAD(cast<LoadSDNode>(N));break;
60   case ISD::SCALAR_TO_VECTOR:  R = ScalarizeVecRes_SCALAR_TO_VECTOR(N); break;
61   case ISD::SIGN_EXTEND_INREG: R = ScalarizeVecRes_InregOp(N); break;
62   case ISD::VSELECT:           R = ScalarizeVecRes_VSELECT(N); break;
63   case ISD::SELECT:            R = ScalarizeVecRes_SELECT(N); break;
64   case ISD::SELECT_CC:         R = ScalarizeVecRes_SELECT_CC(N); break;
65   case ISD::SETCC:             R = ScalarizeVecRes_SETCC(N); break;
66   case ISD::UNDEF:             R = ScalarizeVecRes_UNDEF(N); break;
67   case ISD::VECTOR_SHUFFLE:    R = ScalarizeVecRes_VECTOR_SHUFFLE(N); break;
68   case ISD::ANY_EXTEND_VECTOR_INREG:
69   case ISD::SIGN_EXTEND_VECTOR_INREG:
70   case ISD::ZERO_EXTEND_VECTOR_INREG:
71     R = ScalarizeVecRes_VecInregOp(N);
72     break;
73   case ISD::ANY_EXTEND:
74   case ISD::BITREVERSE:
75   case ISD::BSWAP:
76   case ISD::CTLZ:
77   case ISD::CTLZ_ZERO_UNDEF:
78   case ISD::CTPOP:
79   case ISD::CTTZ:
80   case ISD::CTTZ_ZERO_UNDEF:
81   case ISD::FABS:
82   case ISD::FCEIL:
83   case ISD::FCOS:
84   case ISD::FEXP:
85   case ISD::FEXP2:
86   case ISD::FFLOOR:
87   case ISD::FLOG:
88   case ISD::FLOG10:
89   case ISD::FLOG2:
90   case ISD::FNEARBYINT:
91   case ISD::FNEG:
92   case ISD::FP_EXTEND:
93   case ISD::FP_TO_SINT:
94   case ISD::FP_TO_UINT:
95   case ISD::FRINT:
96   case ISD::FROUND:
97   case ISD::FSIN:
98   case ISD::FSQRT:
99   case ISD::FTRUNC:
100   case ISD::SIGN_EXTEND:
101   case ISD::SINT_TO_FP:
102   case ISD::TRUNCATE:
103   case ISD::UINT_TO_FP:
104   case ISD::ZERO_EXTEND:
105   case ISD::FCANONICALIZE:
106     R = ScalarizeVecRes_UnaryOp(N);
107     break;
108
109   case ISD::ADD:
110   case ISD::AND:
111   case ISD::FADD:
112   case ISD::FCOPYSIGN:
113   case ISD::FDIV:
114   case ISD::FMUL:
115   case ISD::FMINNUM:
116   case ISD::FMAXNUM:
117   case ISD::FMINNAN:
118   case ISD::FMAXNAN:
119   case ISD::SMIN:
120   case ISD::SMAX:
121   case ISD::UMIN:
122   case ISD::UMAX:
123
124   case ISD::FPOW:
125   case ISD::FREM:
126   case ISD::FSUB:
127   case ISD::MUL:
128   case ISD::OR:
129   case ISD::SDIV:
130   case ISD::SREM:
131   case ISD::SUB:
132   case ISD::UDIV:
133   case ISD::UREM:
134   case ISD::XOR:
135   case ISD::SHL:
136   case ISD::SRA:
137   case ISD::SRL:
138     R = ScalarizeVecRes_BinOp(N);
139     break;
140   case ISD::FMA:
141     R = ScalarizeVecRes_TernaryOp(N);
142     break;
143   }
144
145   // If R is null, the sub-method took care of registering the result.
146   if (R.getNode())
147     SetScalarizedVector(SDValue(N, ResNo), R);
148 }
149
150 SDValue DAGTypeLegalizer::ScalarizeVecRes_BinOp(SDNode *N) {
151   SDValue LHS = GetScalarizedVector(N->getOperand(0));
152   SDValue RHS = GetScalarizedVector(N->getOperand(1));
153   return DAG.getNode(N->getOpcode(), SDLoc(N),
154                      LHS.getValueType(), LHS, RHS, N->getFlags());
155 }
156
157 SDValue DAGTypeLegalizer::ScalarizeVecRes_TernaryOp(SDNode *N) {
158   SDValue Op0 = GetScalarizedVector(N->getOperand(0));
159   SDValue Op1 = GetScalarizedVector(N->getOperand(1));
160   SDValue Op2 = GetScalarizedVector(N->getOperand(2));
161   return DAG.getNode(N->getOpcode(), SDLoc(N),
162                      Op0.getValueType(), Op0, Op1, Op2);
163 }
164
165 SDValue DAGTypeLegalizer::ScalarizeVecRes_MERGE_VALUES(SDNode *N,
166                                                        unsigned ResNo) {
167   SDValue Op = DisintegrateMERGE_VALUES(N, ResNo);
168   return GetScalarizedVector(Op);
169 }
170
171 SDValue DAGTypeLegalizer::ScalarizeVecRes_BITCAST(SDNode *N) {
172   EVT NewVT = N->getValueType(0).getVectorElementType();
173   return DAG.getNode(ISD::BITCAST, SDLoc(N),
174                      NewVT, N->getOperand(0));
175 }
176
177 SDValue DAGTypeLegalizer::ScalarizeVecRes_BUILD_VECTOR(SDNode *N) {
178   EVT EltVT = N->getValueType(0).getVectorElementType();
179   SDValue InOp = N->getOperand(0);
180   // The BUILD_VECTOR operands may be of wider element types and
181   // we may need to truncate them back to the requested return type.
182   if (EltVT.isInteger())
183     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
184   return InOp;
185 }
186
187 SDValue DAGTypeLegalizer::ScalarizeVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
188   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
189                      N->getValueType(0).getVectorElementType(),
190                      N->getOperand(0), N->getOperand(1));
191 }
192
193 SDValue DAGTypeLegalizer::ScalarizeVecRes_FP_ROUND(SDNode *N) {
194   EVT NewVT = N->getValueType(0).getVectorElementType();
195   SDValue Op = GetScalarizedVector(N->getOperand(0));
196   return DAG.getNode(ISD::FP_ROUND, SDLoc(N),
197                      NewVT, Op, N->getOperand(1));
198 }
199
200 SDValue DAGTypeLegalizer::ScalarizeVecRes_FPOWI(SDNode *N) {
201   SDValue Op = GetScalarizedVector(N->getOperand(0));
202   return DAG.getNode(ISD::FPOWI, SDLoc(N),
203                      Op.getValueType(), Op, N->getOperand(1));
204 }
205
206 SDValue DAGTypeLegalizer::ScalarizeVecRes_INSERT_VECTOR_ELT(SDNode *N) {
207   // The value to insert may have a wider type than the vector element type,
208   // so be sure to truncate it to the element type if necessary.
209   SDValue Op = N->getOperand(1);
210   EVT EltVT = N->getValueType(0).getVectorElementType();
211   if (Op.getValueType() != EltVT)
212     // FIXME: Can this happen for floating point types?
213     Op = DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, Op);
214   return Op;
215 }
216
217 SDValue DAGTypeLegalizer::ScalarizeVecRes_LOAD(LoadSDNode *N) {
218   assert(N->isUnindexed() && "Indexed vector load?");
219
220   SDValue Result = DAG.getLoad(
221       ISD::UNINDEXED, N->getExtensionType(),
222       N->getValueType(0).getVectorElementType(), SDLoc(N), N->getChain(),
223       N->getBasePtr(), DAG.getUNDEF(N->getBasePtr().getValueType()),
224       N->getPointerInfo(), N->getMemoryVT().getVectorElementType(),
225       N->getOriginalAlignment(), N->getMemOperand()->getFlags(),
226       N->getAAInfo());
227
228   // Legalize the chain result - switch anything that used the old chain to
229   // use the new one.
230   ReplaceValueWith(SDValue(N, 1), Result.getValue(1));
231   return Result;
232 }
233
234 SDValue DAGTypeLegalizer::ScalarizeVecRes_UnaryOp(SDNode *N) {
235   // Get the dest type - it doesn't always match the input type, e.g. int_to_fp.
236   EVT DestVT = N->getValueType(0).getVectorElementType();
237   SDValue Op = N->getOperand(0);
238   EVT OpVT = Op.getValueType();
239   SDLoc DL(N);
240   // The result needs scalarizing, but it's not a given that the source does.
241   // This is a workaround for targets where it's impossible to scalarize the
242   // result of a conversion, because the source type is legal.
243   // For instance, this happens on AArch64: v1i1 is illegal but v1i{8,16,32}
244   // are widened to v8i8, v4i16, and v2i32, which is legal, because v1i64 is
245   // legal and was not scalarized.
246   // See the similar logic in ScalarizeVecRes_VSETCC
247   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
248     Op = GetScalarizedVector(Op);
249   } else {
250     EVT VT = OpVT.getVectorElementType();
251     Op = DAG.getNode(
252         ISD::EXTRACT_VECTOR_ELT, DL, VT, Op,
253         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
254   }
255   return DAG.getNode(N->getOpcode(), SDLoc(N), DestVT, Op);
256 }
257
258 SDValue DAGTypeLegalizer::ScalarizeVecRes_InregOp(SDNode *N) {
259   EVT EltVT = N->getValueType(0).getVectorElementType();
260   EVT ExtVT = cast<VTSDNode>(N->getOperand(1))->getVT().getVectorElementType();
261   SDValue LHS = GetScalarizedVector(N->getOperand(0));
262   return DAG.getNode(N->getOpcode(), SDLoc(N), EltVT,
263                      LHS, DAG.getValueType(ExtVT));
264 }
265
266 SDValue DAGTypeLegalizer::ScalarizeVecRes_VecInregOp(SDNode *N) {
267   SDLoc DL(N);
268   SDValue Op = N->getOperand(0);
269
270   EVT OpVT = Op.getValueType();
271   EVT OpEltVT = OpVT.getVectorElementType();
272   EVT EltVT = N->getValueType(0).getVectorElementType();
273
274   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
275     Op = GetScalarizedVector(Op);
276   } else {
277     Op = DAG.getNode(
278         ISD::EXTRACT_VECTOR_ELT, DL, OpEltVT, Op,
279         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
280   }
281
282   switch (N->getOpcode()) {
283   case ISD::ANY_EXTEND_VECTOR_INREG:
284     return DAG.getNode(ISD::ANY_EXTEND, DL, EltVT, Op);
285   case ISD::SIGN_EXTEND_VECTOR_INREG:
286     return DAG.getNode(ISD::SIGN_EXTEND, DL, EltVT, Op);
287   case ISD::ZERO_EXTEND_VECTOR_INREG:
288     return DAG.getNode(ISD::ZERO_EXTEND, DL, EltVT, Op);
289   }
290
291   llvm_unreachable("Illegal extend_vector_inreg opcode");
292 }
293
294 SDValue DAGTypeLegalizer::ScalarizeVecRes_SCALAR_TO_VECTOR(SDNode *N) {
295   // If the operand is wider than the vector element type then it is implicitly
296   // truncated.  Make that explicit here.
297   EVT EltVT = N->getValueType(0).getVectorElementType();
298   SDValue InOp = N->getOperand(0);
299   if (InOp.getValueType() != EltVT)
300     return DAG.getNode(ISD::TRUNCATE, SDLoc(N), EltVT, InOp);
301   return InOp;
302 }
303
304 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSELECT(SDNode *N) {
305   SDValue Cond = N->getOperand(0);
306   EVT OpVT = Cond.getValueType();
307   SDLoc DL(N);
308   // The vselect result and true/value operands needs scalarizing, but it's
309   // not a given that the Cond does. For instance, in AVX512 v1i1 is legal.
310   // See the similar logic in ScalarizeVecRes_VSETCC
311   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
312     Cond = GetScalarizedVector(Cond);
313   } else {
314     EVT VT = OpVT.getVectorElementType();
315     Cond = DAG.getNode(
316         ISD::EXTRACT_VECTOR_ELT, DL, VT, Cond,
317         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
318   }
319
320   SDValue LHS = GetScalarizedVector(N->getOperand(1));
321   TargetLowering::BooleanContent ScalarBool =
322       TLI.getBooleanContents(false, false);
323   TargetLowering::BooleanContent VecBool = TLI.getBooleanContents(true, false);
324
325   // If integer and float booleans have different contents then we can't
326   // reliably optimize in all cases. There is a full explanation for this in
327   // DAGCombiner::visitSELECT() where the same issue affects folding
328   // (select C, 0, 1) to (xor C, 1).
329   if (TLI.getBooleanContents(false, false) !=
330       TLI.getBooleanContents(false, true)) {
331     // At least try the common case where the boolean is generated by a
332     // comparison.
333     if (Cond->getOpcode() == ISD::SETCC) {
334       EVT OpVT = Cond->getOperand(0)->getValueType(0);
335       ScalarBool = TLI.getBooleanContents(OpVT.getScalarType());
336       VecBool = TLI.getBooleanContents(OpVT);
337     } else
338       ScalarBool = TargetLowering::UndefinedBooleanContent;
339   }
340
341   if (ScalarBool != VecBool) {
342     EVT CondVT = Cond.getValueType();
343     switch (ScalarBool) {
344       case TargetLowering::UndefinedBooleanContent:
345         break;
346       case TargetLowering::ZeroOrOneBooleanContent:
347         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
348                VecBool == TargetLowering::ZeroOrNegativeOneBooleanContent);
349         // Vector read from all ones, scalar expects a single 1 so mask.
350         Cond = DAG.getNode(ISD::AND, SDLoc(N), CondVT,
351                            Cond, DAG.getConstant(1, SDLoc(N), CondVT));
352         break;
353       case TargetLowering::ZeroOrNegativeOneBooleanContent:
354         assert(VecBool == TargetLowering::UndefinedBooleanContent ||
355                VecBool == TargetLowering::ZeroOrOneBooleanContent);
356         // Vector reads from a one, scalar from all ones so sign extend.
357         Cond = DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N), CondVT,
358                            Cond, DAG.getValueType(MVT::i1));
359         break;
360     }
361   }
362
363   return DAG.getSelect(SDLoc(N),
364                        LHS.getValueType(), Cond, LHS,
365                        GetScalarizedVector(N->getOperand(2)));
366 }
367
368 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT(SDNode *N) {
369   SDValue LHS = GetScalarizedVector(N->getOperand(1));
370   return DAG.getSelect(SDLoc(N),
371                        LHS.getValueType(), N->getOperand(0), LHS,
372                        GetScalarizedVector(N->getOperand(2)));
373 }
374
375 SDValue DAGTypeLegalizer::ScalarizeVecRes_SELECT_CC(SDNode *N) {
376   SDValue LHS = GetScalarizedVector(N->getOperand(2));
377   return DAG.getNode(ISD::SELECT_CC, SDLoc(N), LHS.getValueType(),
378                      N->getOperand(0), N->getOperand(1),
379                      LHS, GetScalarizedVector(N->getOperand(3)),
380                      N->getOperand(4));
381 }
382
383 SDValue DAGTypeLegalizer::ScalarizeVecRes_SETCC(SDNode *N) {
384   assert(N->getValueType(0).isVector() ==
385          N->getOperand(0).getValueType().isVector() &&
386          "Scalar/Vector type mismatch");
387
388   if (N->getValueType(0).isVector()) return ScalarizeVecRes_VSETCC(N);
389
390   SDValue LHS = GetScalarizedVector(N->getOperand(0));
391   SDValue RHS = GetScalarizedVector(N->getOperand(1));
392   SDLoc DL(N);
393
394   // Turn it into a scalar SETCC.
395   return DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS, N->getOperand(2));
396 }
397
398 SDValue DAGTypeLegalizer::ScalarizeVecRes_UNDEF(SDNode *N) {
399   return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
400 }
401
402 SDValue DAGTypeLegalizer::ScalarizeVecRes_VECTOR_SHUFFLE(SDNode *N) {
403   // Figure out if the scalar is the LHS or RHS and return it.
404   SDValue Arg = N->getOperand(2).getOperand(0);
405   if (Arg.isUndef())
406     return DAG.getUNDEF(N->getValueType(0).getVectorElementType());
407   unsigned Op = !cast<ConstantSDNode>(Arg)->isNullValue();
408   return GetScalarizedVector(N->getOperand(Op));
409 }
410
411 SDValue DAGTypeLegalizer::ScalarizeVecRes_VSETCC(SDNode *N) {
412   assert(N->getValueType(0).isVector() &&
413          N->getOperand(0).getValueType().isVector() &&
414          "Operand types must be vectors");
415   SDValue LHS = N->getOperand(0);
416   SDValue RHS = N->getOperand(1);
417   EVT OpVT = LHS.getValueType();
418   EVT NVT = N->getValueType(0).getVectorElementType();
419   SDLoc DL(N);
420
421   // The result needs scalarizing, but it's not a given that the source does.
422   if (getTypeAction(OpVT) == TargetLowering::TypeScalarizeVector) {
423     LHS = GetScalarizedVector(LHS);
424     RHS = GetScalarizedVector(RHS);
425   } else {
426     EVT VT = OpVT.getVectorElementType();
427     LHS = DAG.getNode(
428         ISD::EXTRACT_VECTOR_ELT, DL, VT, LHS,
429         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
430     RHS = DAG.getNode(
431         ISD::EXTRACT_VECTOR_ELT, DL, VT, RHS,
432         DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
433   }
434
435   // Turn it into a scalar SETCC.
436   SDValue Res = DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS,
437                             N->getOperand(2));
438   // Vectors may have a different boolean contents to scalars.  Promote the
439   // value appropriately.
440   ISD::NodeType ExtendCode =
441       TargetLowering::getExtendForContent(TLI.getBooleanContents(OpVT));
442   return DAG.getNode(ExtendCode, DL, NVT, Res);
443 }
444
445
446 //===----------------------------------------------------------------------===//
447 //  Operand Vector Scalarization <1 x ty> -> ty.
448 //===----------------------------------------------------------------------===//
449
450 bool DAGTypeLegalizer::ScalarizeVectorOperand(SDNode *N, unsigned OpNo) {
451   DEBUG(dbgs() << "Scalarize node operand " << OpNo << ": ";
452         N->dump(&DAG);
453         dbgs() << "\n");
454   SDValue Res = SDValue();
455
456   if (!Res.getNode()) {
457     switch (N->getOpcode()) {
458     default:
459 #ifndef NDEBUG
460       dbgs() << "ScalarizeVectorOperand Op #" << OpNo << ": ";
461       N->dump(&DAG);
462       dbgs() << "\n";
463 #endif
464       llvm_unreachable("Do not know how to scalarize this operator's operand!");
465     case ISD::BITCAST:
466       Res = ScalarizeVecOp_BITCAST(N);
467       break;
468     case ISD::ANY_EXTEND:
469     case ISD::ZERO_EXTEND:
470     case ISD::SIGN_EXTEND:
471     case ISD::TRUNCATE:
472     case ISD::FP_TO_SINT:
473     case ISD::FP_TO_UINT:
474     case ISD::SINT_TO_FP:
475     case ISD::UINT_TO_FP:
476       Res = ScalarizeVecOp_UnaryOp(N);
477       break;
478     case ISD::CONCAT_VECTORS:
479       Res = ScalarizeVecOp_CONCAT_VECTORS(N);
480       break;
481     case ISD::EXTRACT_VECTOR_ELT:
482       Res = ScalarizeVecOp_EXTRACT_VECTOR_ELT(N);
483       break;
484     case ISD::VSELECT:
485       Res = ScalarizeVecOp_VSELECT(N);
486       break;
487     case ISD::SETCC:
488       Res = ScalarizeVecOp_VSETCC(N);
489       break;
490     case ISD::STORE:
491       Res = ScalarizeVecOp_STORE(cast<StoreSDNode>(N), OpNo);
492       break;
493     case ISD::FP_ROUND:
494       Res = ScalarizeVecOp_FP_ROUND(N, OpNo);
495       break;
496     }
497   }
498
499   // If the result is null, the sub-method took care of registering results etc.
500   if (!Res.getNode()) return false;
501
502   // If the result is N, the sub-method updated N in place.  Tell the legalizer
503   // core about this.
504   if (Res.getNode() == N)
505     return true;
506
507   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
508          "Invalid operand expansion");
509
510   ReplaceValueWith(SDValue(N, 0), Res);
511   return false;
512 }
513
514 /// If the value to convert is a vector that needs to be scalarized, it must be
515 /// <1 x ty>. Convert the element instead.
516 SDValue DAGTypeLegalizer::ScalarizeVecOp_BITCAST(SDNode *N) {
517   SDValue Elt = GetScalarizedVector(N->getOperand(0));
518   return DAG.getNode(ISD::BITCAST, SDLoc(N),
519                      N->getValueType(0), Elt);
520 }
521
522 /// If the input is a vector that needs to be scalarized, it must be <1 x ty>.
523 /// Do the operation on the element instead.
524 SDValue DAGTypeLegalizer::ScalarizeVecOp_UnaryOp(SDNode *N) {
525   assert(N->getValueType(0).getVectorNumElements() == 1 &&
526          "Unexpected vector type!");
527   SDValue Elt = GetScalarizedVector(N->getOperand(0));
528   SDValue Op = DAG.getNode(N->getOpcode(), SDLoc(N),
529                            N->getValueType(0).getScalarType(), Elt);
530   // Revectorize the result so the types line up with what the uses of this
531   // expression expect.
532   return DAG.getBuildVector(N->getValueType(0), SDLoc(N), Op);
533 }
534
535 /// The vectors to concatenate have length one - use a BUILD_VECTOR instead.
536 SDValue DAGTypeLegalizer::ScalarizeVecOp_CONCAT_VECTORS(SDNode *N) {
537   SmallVector<SDValue, 8> Ops(N->getNumOperands());
538   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i)
539     Ops[i] = GetScalarizedVector(N->getOperand(i));
540   return DAG.getBuildVector(N->getValueType(0), SDLoc(N), Ops);
541 }
542
543 /// If the input is a vector that needs to be scalarized, it must be <1 x ty>,
544 /// so just return the element, ignoring the index.
545 SDValue DAGTypeLegalizer::ScalarizeVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
546   EVT VT = N->getValueType(0);
547   SDValue Res = GetScalarizedVector(N->getOperand(0));
548   if (Res.getValueType() != VT)
549     Res = VT.isFloatingPoint()
550               ? DAG.getNode(ISD::FP_EXTEND, SDLoc(N), VT, Res)
551               : DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), VT, Res);
552   return Res;
553 }
554
555 /// If the input condition is a vector that needs to be scalarized, it must be
556 /// <1 x i1>, so just convert to a normal ISD::SELECT
557 /// (still with vector output type since that was acceptable if we got here).
558 SDValue DAGTypeLegalizer::ScalarizeVecOp_VSELECT(SDNode *N) {
559   SDValue ScalarCond = GetScalarizedVector(N->getOperand(0));
560   EVT VT = N->getValueType(0);
561
562   return DAG.getNode(ISD::SELECT, SDLoc(N), VT, ScalarCond, N->getOperand(1),
563                      N->getOperand(2));
564 }
565
566 /// If the operand is a vector that needs to be scalarized then the
567 /// result must be v1i1, so just convert to a scalar SETCC and wrap
568 /// with a scalar_to_vector since the res type is legal if we got here
569 SDValue DAGTypeLegalizer::ScalarizeVecOp_VSETCC(SDNode *N) {
570   assert(N->getValueType(0).isVector() &&
571          N->getOperand(0).getValueType().isVector() &&
572          "Operand types must be vectors");
573   assert(N->getValueType(0) == MVT::v1i1 && "Expected v1i1 type");
574
575   EVT VT = N->getValueType(0);
576   SDValue LHS = GetScalarizedVector(N->getOperand(0));
577   SDValue RHS = GetScalarizedVector(N->getOperand(1));
578
579   EVT OpVT = N->getOperand(0).getValueType();
580   EVT NVT = VT.getVectorElementType();
581   SDLoc DL(N);
582   // Turn it into a scalar SETCC.
583   SDValue Res = DAG.getNode(ISD::SETCC, DL, MVT::i1, LHS, RHS,
584       N->getOperand(2));
585
586   // Vectors may have a different boolean contents to scalars.  Promote the
587   // value appropriately.
588   ISD::NodeType ExtendCode =
589       TargetLowering::getExtendForContent(TLI.getBooleanContents(OpVT));
590
591   Res = DAG.getNode(ExtendCode, DL, NVT, Res);
592
593   return DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VT, Res);
594 }
595
596 /// If the value to store is a vector that needs to be scalarized, it must be
597 /// <1 x ty>. Just store the element.
598 SDValue DAGTypeLegalizer::ScalarizeVecOp_STORE(StoreSDNode *N, unsigned OpNo){
599   assert(N->isUnindexed() && "Indexed store of one-element vector?");
600   assert(OpNo == 1 && "Do not know how to scalarize this operand!");
601   SDLoc dl(N);
602
603   if (N->isTruncatingStore())
604     return DAG.getTruncStore(
605         N->getChain(), dl, GetScalarizedVector(N->getOperand(1)),
606         N->getBasePtr(), N->getPointerInfo(),
607         N->getMemoryVT().getVectorElementType(), N->getAlignment(),
608         N->getMemOperand()->getFlags(), N->getAAInfo());
609
610   return DAG.getStore(N->getChain(), dl, GetScalarizedVector(N->getOperand(1)),
611                       N->getBasePtr(), N->getPointerInfo(),
612                       N->getOriginalAlignment(), N->getMemOperand()->getFlags(),
613                       N->getAAInfo());
614 }
615
616 /// If the value to round is a vector that needs to be scalarized, it must be
617 /// <1 x ty>. Convert the element instead.
618 SDValue DAGTypeLegalizer::ScalarizeVecOp_FP_ROUND(SDNode *N, unsigned OpNo) {
619   SDValue Elt = GetScalarizedVector(N->getOperand(0));
620   SDValue Res = DAG.getNode(ISD::FP_ROUND, SDLoc(N),
621                             N->getValueType(0).getVectorElementType(), Elt,
622                             N->getOperand(1));
623   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N), N->getValueType(0), Res);
624 }
625
626 //===----------------------------------------------------------------------===//
627 //  Result Vector Splitting
628 //===----------------------------------------------------------------------===//
629
630 /// This method is called when the specified result of the specified node is
631 /// found to need vector splitting. At this point, the node may also have
632 /// invalid operands or may have other results that need legalization, we just
633 /// know that (at least) one result needs vector splitting.
634 void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) {
635   DEBUG(dbgs() << "Split node result: ";
636         N->dump(&DAG);
637         dbgs() << "\n");
638   SDValue Lo, Hi;
639
640   // See if the target wants to custom expand this node.
641   if (CustomLowerNode(N, N->getValueType(ResNo), true))
642     return;
643
644   switch (N->getOpcode()) {
645   default:
646 #ifndef NDEBUG
647     dbgs() << "SplitVectorResult #" << ResNo << ": ";
648     N->dump(&DAG);
649     dbgs() << "\n";
650 #endif
651     report_fatal_error("Do not know how to split the result of this "
652                        "operator!\n");
653
654   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, ResNo, Lo, Hi); break;
655   case ISD::VSELECT:
656   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
657   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
658   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
659   case ISD::BITCAST:           SplitVecRes_BITCAST(N, Lo, Hi); break;
660   case ISD::BUILD_VECTOR:      SplitVecRes_BUILD_VECTOR(N, Lo, Hi); break;
661   case ISD::CONCAT_VECTORS:    SplitVecRes_CONCAT_VECTORS(N, Lo, Hi); break;
662   case ISD::EXTRACT_SUBVECTOR: SplitVecRes_EXTRACT_SUBVECTOR(N, Lo, Hi); break;
663   case ISD::INSERT_SUBVECTOR:  SplitVecRes_INSERT_SUBVECTOR(N, Lo, Hi); break;
664   case ISD::FP_ROUND_INREG:    SplitVecRes_InregOp(N, Lo, Hi); break;
665   case ISD::FPOWI:             SplitVecRes_FPOWI(N, Lo, Hi); break;
666   case ISD::FCOPYSIGN:         SplitVecRes_FCOPYSIGN(N, Lo, Hi); break;
667   case ISD::INSERT_VECTOR_ELT: SplitVecRes_INSERT_VECTOR_ELT(N, Lo, Hi); break;
668   case ISD::SCALAR_TO_VECTOR:  SplitVecRes_SCALAR_TO_VECTOR(N, Lo, Hi); break;
669   case ISD::SIGN_EXTEND_INREG: SplitVecRes_InregOp(N, Lo, Hi); break;
670   case ISD::LOAD:
671     SplitVecRes_LOAD(cast<LoadSDNode>(N), Lo, Hi);
672     break;
673   case ISD::MLOAD:
674     SplitVecRes_MLOAD(cast<MaskedLoadSDNode>(N), Lo, Hi);
675     break;
676   case ISD::MGATHER:
677     SplitVecRes_MGATHER(cast<MaskedGatherSDNode>(N), Lo, Hi);
678     break;
679   case ISD::SETCC:
680     SplitVecRes_SETCC(N, Lo, Hi);
681     break;
682   case ISD::VECTOR_SHUFFLE:
683     SplitVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N), Lo, Hi);
684     break;
685
686   case ISD::ANY_EXTEND_VECTOR_INREG:
687   case ISD::SIGN_EXTEND_VECTOR_INREG:
688   case ISD::ZERO_EXTEND_VECTOR_INREG:
689     SplitVecRes_ExtVecInRegOp(N, Lo, Hi);
690     break;
691
692   case ISD::BITREVERSE:
693   case ISD::BSWAP:
694   case ISD::CTLZ:
695   case ISD::CTTZ:
696   case ISD::CTLZ_ZERO_UNDEF:
697   case ISD::CTTZ_ZERO_UNDEF:
698   case ISD::CTPOP:
699   case ISD::FABS:
700   case ISD::FCEIL:
701   case ISD::FCOS:
702   case ISD::FEXP:
703   case ISD::FEXP2:
704   case ISD::FFLOOR:
705   case ISD::FLOG:
706   case ISD::FLOG10:
707   case ISD::FLOG2:
708   case ISD::FNEARBYINT:
709   case ISD::FNEG:
710   case ISD::FP_EXTEND:
711   case ISD::FP_ROUND:
712   case ISD::FP_TO_SINT:
713   case ISD::FP_TO_UINT:
714   case ISD::FRINT:
715   case ISD::FROUND:
716   case ISD::FSIN:
717   case ISD::FSQRT:
718   case ISD::FTRUNC:
719   case ISD::SINT_TO_FP:
720   case ISD::TRUNCATE:
721   case ISD::UINT_TO_FP:
722   case ISD::FCANONICALIZE:
723     SplitVecRes_UnaryOp(N, Lo, Hi);
724     break;
725
726   case ISD::ANY_EXTEND:
727   case ISD::SIGN_EXTEND:
728   case ISD::ZERO_EXTEND:
729     SplitVecRes_ExtendOp(N, Lo, Hi);
730     break;
731
732   case ISD::ADD:
733   case ISD::SUB:
734   case ISD::MUL:
735   case ISD::MULHS:
736   case ISD::MULHU:
737   case ISD::FADD:
738   case ISD::FSUB:
739   case ISD::FMUL:
740   case ISD::FMINNUM:
741   case ISD::FMAXNUM:
742   case ISD::FMINNAN:
743   case ISD::FMAXNAN:
744   case ISD::SDIV:
745   case ISD::UDIV:
746   case ISD::FDIV:
747   case ISD::FPOW:
748   case ISD::AND:
749   case ISD::OR:
750   case ISD::XOR:
751   case ISD::SHL:
752   case ISD::SRA:
753   case ISD::SRL:
754   case ISD::UREM:
755   case ISD::SREM:
756   case ISD::FREM:
757   case ISD::SMIN:
758   case ISD::SMAX:
759   case ISD::UMIN:
760   case ISD::UMAX:
761     SplitVecRes_BinOp(N, Lo, Hi);
762     break;
763   case ISD::FMA:
764     SplitVecRes_TernaryOp(N, Lo, Hi);
765     break;
766   }
767
768   // If Lo/Hi is null, the sub-method took care of registering results etc.
769   if (Lo.getNode())
770     SetSplitVector(SDValue(N, ResNo), Lo, Hi);
771 }
772
773 void DAGTypeLegalizer::SplitVecRes_BinOp(SDNode *N, SDValue &Lo,
774                                          SDValue &Hi) {
775   SDValue LHSLo, LHSHi;
776   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
777   SDValue RHSLo, RHSHi;
778   GetSplitVector(N->getOperand(1), RHSLo, RHSHi);
779   SDLoc dl(N);
780
781   const SDNodeFlags Flags = N->getFlags();
782   unsigned Opcode = N->getOpcode();
783   Lo = DAG.getNode(Opcode, dl, LHSLo.getValueType(), LHSLo, RHSLo, Flags);
784   Hi = DAG.getNode(Opcode, dl, LHSHi.getValueType(), LHSHi, RHSHi, Flags);
785 }
786
787 void DAGTypeLegalizer::SplitVecRes_TernaryOp(SDNode *N, SDValue &Lo,
788                                              SDValue &Hi) {
789   SDValue Op0Lo, Op0Hi;
790   GetSplitVector(N->getOperand(0), Op0Lo, Op0Hi);
791   SDValue Op1Lo, Op1Hi;
792   GetSplitVector(N->getOperand(1), Op1Lo, Op1Hi);
793   SDValue Op2Lo, Op2Hi;
794   GetSplitVector(N->getOperand(2), Op2Lo, Op2Hi);
795   SDLoc dl(N);
796
797   Lo = DAG.getNode(N->getOpcode(), dl, Op0Lo.getValueType(),
798                    Op0Lo, Op1Lo, Op2Lo);
799   Hi = DAG.getNode(N->getOpcode(), dl, Op0Hi.getValueType(),
800                    Op0Hi, Op1Hi, Op2Hi);
801 }
802
803 void DAGTypeLegalizer::SplitVecRes_BITCAST(SDNode *N, SDValue &Lo,
804                                            SDValue &Hi) {
805   // We know the result is a vector.  The input may be either a vector or a
806   // scalar value.
807   EVT LoVT, HiVT;
808   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
809   SDLoc dl(N);
810
811   SDValue InOp = N->getOperand(0);
812   EVT InVT = InOp.getValueType();
813
814   // Handle some special cases efficiently.
815   switch (getTypeAction(InVT)) {
816   case TargetLowering::TypeLegal:
817   case TargetLowering::TypePromoteInteger:
818   case TargetLowering::TypePromoteFloat:
819   case TargetLowering::TypeSoftenFloat:
820   case TargetLowering::TypeScalarizeVector:
821   case TargetLowering::TypeWidenVector:
822     break;
823   case TargetLowering::TypeExpandInteger:
824   case TargetLowering::TypeExpandFloat:
825     // A scalar to vector conversion, where the scalar needs expansion.
826     // If the vector is being split in two then we can just convert the
827     // expanded pieces.
828     if (LoVT == HiVT) {
829       GetExpandedOp(InOp, Lo, Hi);
830       if (DAG.getDataLayout().isBigEndian())
831         std::swap(Lo, Hi);
832       Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
833       Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
834       return;
835     }
836     break;
837   case TargetLowering::TypeSplitVector:
838     // If the input is a vector that needs to be split, convert each split
839     // piece of the input now.
840     GetSplitVector(InOp, Lo, Hi);
841     Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
842     Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
843     return;
844   }
845
846   // In the general case, convert the input to an integer and split it by hand.
847   EVT LoIntVT = EVT::getIntegerVT(*DAG.getContext(), LoVT.getSizeInBits());
848   EVT HiIntVT = EVT::getIntegerVT(*DAG.getContext(), HiVT.getSizeInBits());
849   if (DAG.getDataLayout().isBigEndian())
850     std::swap(LoIntVT, HiIntVT);
851
852   SplitInteger(BitConvertToInteger(InOp), LoIntVT, HiIntVT, Lo, Hi);
853
854   if (DAG.getDataLayout().isBigEndian())
855     std::swap(Lo, Hi);
856   Lo = DAG.getNode(ISD::BITCAST, dl, LoVT, Lo);
857   Hi = DAG.getNode(ISD::BITCAST, dl, HiVT, Hi);
858 }
859
860 void DAGTypeLegalizer::SplitVecRes_BUILD_VECTOR(SDNode *N, SDValue &Lo,
861                                                 SDValue &Hi) {
862   EVT LoVT, HiVT;
863   SDLoc dl(N);
864   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
865   unsigned LoNumElts = LoVT.getVectorNumElements();
866   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+LoNumElts);
867   Lo = DAG.getBuildVector(LoVT, dl, LoOps);
868
869   SmallVector<SDValue, 8> HiOps(N->op_begin()+LoNumElts, N->op_end());
870   Hi = DAG.getBuildVector(HiVT, dl, HiOps);
871 }
872
873 void DAGTypeLegalizer::SplitVecRes_CONCAT_VECTORS(SDNode *N, SDValue &Lo,
874                                                   SDValue &Hi) {
875   assert(!(N->getNumOperands() & 1) && "Unsupported CONCAT_VECTORS");
876   SDLoc dl(N);
877   unsigned NumSubvectors = N->getNumOperands() / 2;
878   if (NumSubvectors == 1) {
879     Lo = N->getOperand(0);
880     Hi = N->getOperand(1);
881     return;
882   }
883
884   EVT LoVT, HiVT;
885   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
886
887   SmallVector<SDValue, 8> LoOps(N->op_begin(), N->op_begin()+NumSubvectors);
888   Lo = DAG.getNode(ISD::CONCAT_VECTORS, dl, LoVT, LoOps);
889
890   SmallVector<SDValue, 8> HiOps(N->op_begin()+NumSubvectors, N->op_end());
891   Hi = DAG.getNode(ISD::CONCAT_VECTORS, dl, HiVT, HiOps);
892 }
893
894 void DAGTypeLegalizer::SplitVecRes_EXTRACT_SUBVECTOR(SDNode *N, SDValue &Lo,
895                                                      SDValue &Hi) {
896   SDValue Vec = N->getOperand(0);
897   SDValue Idx = N->getOperand(1);
898   SDLoc dl(N);
899
900   EVT LoVT, HiVT;
901   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
902
903   Lo = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, LoVT, Vec, Idx);
904   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
905   Hi = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, HiVT, Vec,
906                    DAG.getConstant(IdxVal + LoVT.getVectorNumElements(), dl,
907                                    TLI.getVectorIdxTy(DAG.getDataLayout())));
908 }
909
910 void DAGTypeLegalizer::SplitVecRes_INSERT_SUBVECTOR(SDNode *N, SDValue &Lo,
911                                                     SDValue &Hi) {
912   SDValue Vec = N->getOperand(0);
913   SDValue SubVec = N->getOperand(1);
914   SDValue Idx = N->getOperand(2);
915   SDLoc dl(N);
916   GetSplitVector(Vec, Lo, Hi);
917
918   EVT VecVT = Vec.getValueType();
919   unsigned VecElems = VecVT.getVectorNumElements();
920   unsigned SubElems = SubVec.getValueType().getVectorNumElements();
921
922   // If we know the index is 0, and we know the subvector doesn't cross the
923   // boundary between the halves, we can avoid spilling the vector, and insert
924   // into the lower half of the split vector directly.
925   // TODO: The IdxVal == 0 constraint is artificial, we could do this whenever
926   // the index is constant and there is no boundary crossing. But those cases
927   // don't seem to get hit in practice.
928   if (ConstantSDNode *ConstIdx = dyn_cast<ConstantSDNode>(Idx)) {
929     unsigned IdxVal = ConstIdx->getZExtValue();
930     if ((IdxVal == 0) && (IdxVal + SubElems <= VecElems / 2)) {
931       EVT LoVT, HiVT;
932       std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
933       Lo = DAG.getNode(ISD::INSERT_SUBVECTOR, dl, LoVT, Lo, SubVec, Idx);
934       return;
935     }
936   }
937
938   // Spill the vector to the stack.
939   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
940   SDValue Store =
941       DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, MachinePointerInfo());
942
943   // Store the new subvector into the specified index.
944   SDValue SubVecPtr = TLI.getVectorElementPointer(DAG, StackPtr, VecVT, Idx);
945   Type *VecType = VecVT.getTypeForEVT(*DAG.getContext());
946   unsigned Alignment = DAG.getDataLayout().getPrefTypeAlignment(VecType);
947   Store = DAG.getStore(Store, dl, SubVec, SubVecPtr, MachinePointerInfo());
948
949   // Load the Lo part from the stack slot.
950   Lo =
951       DAG.getLoad(Lo.getValueType(), dl, Store, StackPtr, MachinePointerInfo());
952
953   // Increment the pointer to the other part.
954   unsigned IncrementSize = Lo.getValueSizeInBits() / 8;
955   StackPtr =
956       DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
957                   DAG.getConstant(IncrementSize, dl, StackPtr.getValueType()));
958
959   // Load the Hi part from the stack slot.
960   Hi = DAG.getLoad(Hi.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
961                    MinAlign(Alignment, IncrementSize));
962 }
963
964 void DAGTypeLegalizer::SplitVecRes_FPOWI(SDNode *N, SDValue &Lo,
965                                          SDValue &Hi) {
966   SDLoc dl(N);
967   GetSplitVector(N->getOperand(0), Lo, Hi);
968   Lo = DAG.getNode(ISD::FPOWI, dl, Lo.getValueType(), Lo, N->getOperand(1));
969   Hi = DAG.getNode(ISD::FPOWI, dl, Hi.getValueType(), Hi, N->getOperand(1));
970 }
971
972 void DAGTypeLegalizer::SplitVecRes_FCOPYSIGN(SDNode *N, SDValue &Lo,
973                                              SDValue &Hi) {
974   SDValue LHSLo, LHSHi;
975   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
976   SDLoc DL(N);
977
978   SDValue RHSLo, RHSHi;
979   SDValue RHS = N->getOperand(1);
980   EVT RHSVT = RHS.getValueType();
981   if (getTypeAction(RHSVT) == TargetLowering::TypeSplitVector)
982     GetSplitVector(RHS, RHSLo, RHSHi);
983   else
984     std::tie(RHSLo, RHSHi) = DAG.SplitVector(RHS, SDLoc(RHS));
985
986
987   Lo = DAG.getNode(ISD::FCOPYSIGN, DL, LHSLo.getValueType(), LHSLo, RHSLo);
988   Hi = DAG.getNode(ISD::FCOPYSIGN, DL, LHSHi.getValueType(), LHSHi, RHSHi);
989 }
990
991 void DAGTypeLegalizer::SplitVecRes_InregOp(SDNode *N, SDValue &Lo,
992                                            SDValue &Hi) {
993   SDValue LHSLo, LHSHi;
994   GetSplitVector(N->getOperand(0), LHSLo, LHSHi);
995   SDLoc dl(N);
996
997   EVT LoVT, HiVT;
998   std::tie(LoVT, HiVT) =
999     DAG.GetSplitDestVTs(cast<VTSDNode>(N->getOperand(1))->getVT());
1000
1001   Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo,
1002                    DAG.getValueType(LoVT));
1003   Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi,
1004                    DAG.getValueType(HiVT));
1005 }
1006
1007 void DAGTypeLegalizer::SplitVecRes_ExtVecInRegOp(SDNode *N, SDValue &Lo,
1008                                                  SDValue &Hi) {
1009   unsigned Opcode = N->getOpcode();
1010   SDValue N0 = N->getOperand(0);
1011
1012   SDLoc dl(N);
1013   SDValue InLo, InHi;
1014
1015   if (getTypeAction(N0.getValueType()) == TargetLowering::TypeSplitVector)
1016     GetSplitVector(N0, InLo, InHi);
1017   else
1018     std::tie(InLo, InHi) = DAG.SplitVectorOperand(N, 0);
1019
1020   EVT InLoVT = InLo.getValueType();
1021   unsigned InNumElements = InLoVT.getVectorNumElements();
1022
1023   EVT OutLoVT, OutHiVT;
1024   std::tie(OutLoVT, OutHiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1025   unsigned OutNumElements = OutLoVT.getVectorNumElements();
1026   assert((2 * OutNumElements) <= InNumElements &&
1027          "Illegal extend vector in reg split");
1028
1029   // *_EXTEND_VECTOR_INREG instructions extend the lowest elements of the
1030   // input vector (i.e. we only use InLo):
1031   // OutLo will extend the first OutNumElements from InLo.
1032   // OutHi will extend the next OutNumElements from InLo.
1033
1034   // Shuffle the elements from InLo for OutHi into the bottom elements to
1035   // create a 'fake' InHi.
1036   SmallVector<int, 8> SplitHi(InNumElements, -1);
1037   for (unsigned i = 0; i != OutNumElements; ++i)
1038     SplitHi[i] = i + OutNumElements;
1039   InHi = DAG.getVectorShuffle(InLoVT, dl, InLo, DAG.getUNDEF(InLoVT), SplitHi);
1040
1041   Lo = DAG.getNode(Opcode, dl, OutLoVT, InLo);
1042   Hi = DAG.getNode(Opcode, dl, OutHiVT, InHi);
1043 }
1044
1045 void DAGTypeLegalizer::SplitVecRes_INSERT_VECTOR_ELT(SDNode *N, SDValue &Lo,
1046                                                      SDValue &Hi) {
1047   SDValue Vec = N->getOperand(0);
1048   SDValue Elt = N->getOperand(1);
1049   SDValue Idx = N->getOperand(2);
1050   SDLoc dl(N);
1051   GetSplitVector(Vec, Lo, Hi);
1052
1053   if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
1054     unsigned IdxVal = CIdx->getZExtValue();
1055     unsigned LoNumElts = Lo.getValueType().getVectorNumElements();
1056     if (IdxVal < LoNumElts)
1057       Lo = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl,
1058                        Lo.getValueType(), Lo, Elt, Idx);
1059     else
1060       Hi =
1061           DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, Hi.getValueType(), Hi, Elt,
1062                       DAG.getConstant(IdxVal - LoNumElts, dl,
1063                                       TLI.getVectorIdxTy(DAG.getDataLayout())));
1064     return;
1065   }
1066
1067   // See if the target wants to custom expand this node.
1068   if (CustomLowerNode(N, N->getValueType(0), true))
1069     return;
1070
1071   // Spill the vector to the stack.
1072   EVT VecVT = Vec.getValueType();
1073   EVT EltVT = VecVT.getVectorElementType();
1074   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
1075   SDValue Store =
1076       DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, MachinePointerInfo());
1077
1078   // Store the new element.  This may be larger than the vector element type,
1079   // so use a truncating store.
1080   SDValue EltPtr = TLI.getVectorElementPointer(DAG, StackPtr, VecVT, Idx);
1081   Type *VecType = VecVT.getTypeForEVT(*DAG.getContext());
1082   unsigned Alignment = DAG.getDataLayout().getPrefTypeAlignment(VecType);
1083   Store =
1084       DAG.getTruncStore(Store, dl, Elt, EltPtr, MachinePointerInfo(), EltVT);
1085
1086   // Load the Lo part from the stack slot.
1087   Lo =
1088       DAG.getLoad(Lo.getValueType(), dl, Store, StackPtr, MachinePointerInfo());
1089
1090   // Increment the pointer to the other part.
1091   unsigned IncrementSize = Lo.getValueSizeInBits() / 8;
1092   StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
1093                          DAG.getConstant(IncrementSize, dl,
1094                                          StackPtr.getValueType()));
1095
1096   // Load the Hi part from the stack slot.
1097   Hi = DAG.getLoad(Hi.getValueType(), dl, Store, StackPtr, MachinePointerInfo(),
1098                    MinAlign(Alignment, IncrementSize));
1099 }
1100
1101 void DAGTypeLegalizer::SplitVecRes_SCALAR_TO_VECTOR(SDNode *N, SDValue &Lo,
1102                                                     SDValue &Hi) {
1103   EVT LoVT, HiVT;
1104   SDLoc dl(N);
1105   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1106   Lo = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, LoVT, N->getOperand(0));
1107   Hi = DAG.getUNDEF(HiVT);
1108 }
1109
1110 void DAGTypeLegalizer::SplitVecRes_LOAD(LoadSDNode *LD, SDValue &Lo,
1111                                         SDValue &Hi) {
1112   assert(ISD::isUNINDEXEDLoad(LD) && "Indexed load during type legalization!");
1113   EVT LoVT, HiVT;
1114   SDLoc dl(LD);
1115   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(LD->getValueType(0));
1116
1117   ISD::LoadExtType ExtType = LD->getExtensionType();
1118   SDValue Ch = LD->getChain();
1119   SDValue Ptr = LD->getBasePtr();
1120   SDValue Offset = DAG.getUNDEF(Ptr.getValueType());
1121   EVT MemoryVT = LD->getMemoryVT();
1122   unsigned Alignment = LD->getOriginalAlignment();
1123   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
1124   AAMDNodes AAInfo = LD->getAAInfo();
1125
1126   EVT LoMemVT, HiMemVT;
1127   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1128
1129   Lo = DAG.getLoad(ISD::UNINDEXED, ExtType, LoVT, dl, Ch, Ptr, Offset,
1130                    LD->getPointerInfo(), LoMemVT, Alignment, MMOFlags, AAInfo);
1131
1132   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
1133   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
1134                     DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
1135   Hi = DAG.getLoad(ISD::UNINDEXED, ExtType, HiVT, dl, Ch, Ptr, Offset,
1136                    LD->getPointerInfo().getWithOffset(IncrementSize), HiMemVT,
1137                    Alignment, MMOFlags, AAInfo);
1138
1139   // Build a factor node to remember that this load is independent of the
1140   // other one.
1141   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1142                    Hi.getValue(1));
1143
1144   // Legalize the chain result - switch anything that used the old chain to
1145   // use the new one.
1146   ReplaceValueWith(SDValue(LD, 1), Ch);
1147 }
1148
1149 void DAGTypeLegalizer::SplitVecRes_MLOAD(MaskedLoadSDNode *MLD,
1150                                          SDValue &Lo, SDValue &Hi) {
1151   EVT LoVT, HiVT;
1152   SDLoc dl(MLD);
1153   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(MLD->getValueType(0));
1154
1155   SDValue Ch = MLD->getChain();
1156   SDValue Ptr = MLD->getBasePtr();
1157   SDValue Mask = MLD->getMask();
1158   SDValue Src0 = MLD->getSrc0();
1159   unsigned Alignment = MLD->getOriginalAlignment();
1160   ISD::LoadExtType ExtType = MLD->getExtensionType();
1161
1162   // if Alignment is equal to the vector size,
1163   // take the half of it for the second part
1164   unsigned SecondHalfAlignment =
1165     (Alignment == MLD->getValueType(0).getSizeInBits()/8) ?
1166      Alignment/2 : Alignment;
1167
1168   // Split Mask operand
1169   SDValue MaskLo, MaskHi;
1170   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1171     GetSplitVector(Mask, MaskLo, MaskHi);
1172   else
1173     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, dl);
1174
1175   EVT MemoryVT = MLD->getMemoryVT();
1176   EVT LoMemVT, HiMemVT;
1177   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1178
1179   SDValue Src0Lo, Src0Hi;
1180   if (getTypeAction(Src0.getValueType()) == TargetLowering::TypeSplitVector)
1181     GetSplitVector(Src0, Src0Lo, Src0Hi);
1182   else
1183     std::tie(Src0Lo, Src0Hi) = DAG.SplitVector(Src0, dl);
1184
1185   MachineMemOperand *MMO = DAG.getMachineFunction().
1186     getMachineMemOperand(MLD->getPointerInfo(),
1187                          MachineMemOperand::MOLoad,  LoMemVT.getStoreSize(),
1188                          Alignment, MLD->getAAInfo(), MLD->getRanges());
1189
1190   Lo = DAG.getMaskedLoad(LoVT, dl, Ch, Ptr, MaskLo, Src0Lo, LoMemVT, MMO,
1191                          ExtType, MLD->isExpandingLoad());
1192
1193   Ptr = TLI.IncrementMemoryAddress(Ptr, MaskLo, dl, LoMemVT, DAG,
1194                                    MLD->isExpandingLoad());
1195
1196   MMO = DAG.getMachineFunction().
1197     getMachineMemOperand(MLD->getPointerInfo(),
1198                          MachineMemOperand::MOLoad,  HiMemVT.getStoreSize(),
1199                          SecondHalfAlignment, MLD->getAAInfo(), MLD->getRanges());
1200
1201   Hi = DAG.getMaskedLoad(HiVT, dl, Ch, Ptr, MaskHi, Src0Hi, HiMemVT, MMO,
1202                          ExtType, MLD->isExpandingLoad());
1203
1204
1205   // Build a factor node to remember that this load is independent of the
1206   // other one.
1207   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1208                    Hi.getValue(1));
1209
1210   // Legalize the chain result - switch anything that used the old chain to
1211   // use the new one.
1212   ReplaceValueWith(SDValue(MLD, 1), Ch);
1213
1214 }
1215
1216 void DAGTypeLegalizer::SplitVecRes_MGATHER(MaskedGatherSDNode *MGT,
1217                                          SDValue &Lo, SDValue &Hi) {
1218   EVT LoVT, HiVT;
1219   SDLoc dl(MGT);
1220   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(MGT->getValueType(0));
1221
1222   SDValue Ch = MGT->getChain();
1223   SDValue Ptr = MGT->getBasePtr();
1224   SDValue Mask = MGT->getMask();
1225   SDValue Src0 = MGT->getValue();
1226   SDValue Index = MGT->getIndex();
1227   unsigned Alignment = MGT->getOriginalAlignment();
1228
1229   // Split Mask operand
1230   SDValue MaskLo, MaskHi;
1231   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1232     GetSplitVector(Mask, MaskLo, MaskHi);
1233   else
1234     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, dl);
1235
1236   EVT MemoryVT = MGT->getMemoryVT();
1237   EVT LoMemVT, HiMemVT;
1238   // Split MemoryVT
1239   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1240
1241   SDValue Src0Lo, Src0Hi;
1242   if (getTypeAction(Src0.getValueType()) == TargetLowering::TypeSplitVector)
1243     GetSplitVector(Src0, Src0Lo, Src0Hi);
1244   else
1245     std::tie(Src0Lo, Src0Hi) = DAG.SplitVector(Src0, dl);
1246
1247   SDValue IndexHi, IndexLo;
1248   if (getTypeAction(Index.getValueType()) == TargetLowering::TypeSplitVector)
1249     GetSplitVector(Index, IndexLo, IndexHi);
1250   else
1251     std::tie(IndexLo, IndexHi) = DAG.SplitVector(Index, dl);
1252
1253   MachineMemOperand *MMO = DAG.getMachineFunction().
1254     getMachineMemOperand(MGT->getPointerInfo(),
1255                          MachineMemOperand::MOLoad,  LoMemVT.getStoreSize(),
1256                          Alignment, MGT->getAAInfo(), MGT->getRanges());
1257
1258   SDValue OpsLo[] = {Ch, Src0Lo, MaskLo, Ptr, IndexLo};
1259   Lo = DAG.getMaskedGather(DAG.getVTList(LoVT, MVT::Other), LoVT, dl, OpsLo,
1260                            MMO);
1261
1262   SDValue OpsHi[] = {Ch, Src0Hi, MaskHi, Ptr, IndexHi};
1263   Hi = DAG.getMaskedGather(DAG.getVTList(HiVT, MVT::Other), HiVT, dl, OpsHi,
1264                            MMO);
1265
1266   // Build a factor node to remember that this load is independent of the
1267   // other one.
1268   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1269                    Hi.getValue(1));
1270
1271   // Legalize the chain result - switch anything that used the old chain to
1272   // use the new one.
1273   ReplaceValueWith(SDValue(MGT, 1), Ch);
1274 }
1275
1276
1277 void DAGTypeLegalizer::SplitVecRes_SETCC(SDNode *N, SDValue &Lo, SDValue &Hi) {
1278   assert(N->getValueType(0).isVector() &&
1279          N->getOperand(0).getValueType().isVector() &&
1280          "Operand types must be vectors");
1281
1282   EVT LoVT, HiVT;
1283   SDLoc DL(N);
1284   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1285
1286   // Split the input.
1287   SDValue LL, LH, RL, RH;
1288   std::tie(LL, LH) = DAG.SplitVectorOperand(N, 0);
1289   std::tie(RL, RH) = DAG.SplitVectorOperand(N, 1);
1290
1291   Lo = DAG.getNode(N->getOpcode(), DL, LoVT, LL, RL, N->getOperand(2));
1292   Hi = DAG.getNode(N->getOpcode(), DL, HiVT, LH, RH, N->getOperand(2));
1293 }
1294
1295 void DAGTypeLegalizer::SplitVecRes_UnaryOp(SDNode *N, SDValue &Lo,
1296                                            SDValue &Hi) {
1297   // Get the dest types - they may not match the input types, e.g. int_to_fp.
1298   EVT LoVT, HiVT;
1299   SDLoc dl(N);
1300   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
1301
1302   // If the input also splits, handle it directly for a compile time speedup.
1303   // Otherwise split it by hand.
1304   EVT InVT = N->getOperand(0).getValueType();
1305   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector)
1306     GetSplitVector(N->getOperand(0), Lo, Hi);
1307   else
1308     std::tie(Lo, Hi) = DAG.SplitVectorOperand(N, 0);
1309
1310   if (N->getOpcode() == ISD::FP_ROUND) {
1311     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo, N->getOperand(1));
1312     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi, N->getOperand(1));
1313   } else {
1314     Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
1315     Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
1316   }
1317 }
1318
1319 void DAGTypeLegalizer::SplitVecRes_ExtendOp(SDNode *N, SDValue &Lo,
1320                                             SDValue &Hi) {
1321   SDLoc dl(N);
1322   EVT SrcVT = N->getOperand(0).getValueType();
1323   EVT DestVT = N->getValueType(0);
1324   EVT LoVT, HiVT;
1325   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(DestVT);
1326
1327   // We can do better than a generic split operation if the extend is doing
1328   // more than just doubling the width of the elements and the following are
1329   // true:
1330   //   - The number of vector elements is even,
1331   //   - the source type is legal,
1332   //   - the type of a split source is illegal,
1333   //   - the type of an extended (by doubling element size) source is legal, and
1334   //   - the type of that extended source when split is legal.
1335   //
1336   // This won't necessarily completely legalize the operation, but it will
1337   // more effectively move in the right direction and prevent falling down
1338   // to scalarization in many cases due to the input vector being split too
1339   // far.
1340   unsigned NumElements = SrcVT.getVectorNumElements();
1341   if ((NumElements & 1) == 0 &&
1342       SrcVT.getSizeInBits() * 2 < DestVT.getSizeInBits()) {
1343     LLVMContext &Ctx = *DAG.getContext();
1344     EVT NewSrcVT = SrcVT.widenIntegerVectorElementType(Ctx);
1345     EVT SplitSrcVT = SrcVT.getHalfNumVectorElementsVT(Ctx);
1346
1347     EVT SplitLoVT, SplitHiVT;
1348     std::tie(SplitLoVT, SplitHiVT) = DAG.GetSplitDestVTs(NewSrcVT);
1349     if (TLI.isTypeLegal(SrcVT) && !TLI.isTypeLegal(SplitSrcVT) &&
1350         TLI.isTypeLegal(NewSrcVT) && TLI.isTypeLegal(SplitLoVT)) {
1351       DEBUG(dbgs() << "Split vector extend via incremental extend:";
1352             N->dump(&DAG); dbgs() << "\n");
1353       // Extend the source vector by one step.
1354       SDValue NewSrc =
1355           DAG.getNode(N->getOpcode(), dl, NewSrcVT, N->getOperand(0));
1356       // Get the low and high halves of the new, extended one step, vector.
1357       std::tie(Lo, Hi) = DAG.SplitVector(NewSrc, dl);
1358       // Extend those vector halves the rest of the way.
1359       Lo = DAG.getNode(N->getOpcode(), dl, LoVT, Lo);
1360       Hi = DAG.getNode(N->getOpcode(), dl, HiVT, Hi);
1361       return;
1362     }
1363   }
1364   // Fall back to the generic unary operator splitting otherwise.
1365   SplitVecRes_UnaryOp(N, Lo, Hi);
1366 }
1367
1368 void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N,
1369                                                   SDValue &Lo, SDValue &Hi) {
1370   // The low and high parts of the original input give four input vectors.
1371   SDValue Inputs[4];
1372   SDLoc dl(N);
1373   GetSplitVector(N->getOperand(0), Inputs[0], Inputs[1]);
1374   GetSplitVector(N->getOperand(1), Inputs[2], Inputs[3]);
1375   EVT NewVT = Inputs[0].getValueType();
1376   unsigned NewElts = NewVT.getVectorNumElements();
1377
1378   // If Lo or Hi uses elements from at most two of the four input vectors, then
1379   // express it as a vector shuffle of those two inputs.  Otherwise extract the
1380   // input elements by hand and construct the Lo/Hi output using a BUILD_VECTOR.
1381   SmallVector<int, 16> Ops;
1382   for (unsigned High = 0; High < 2; ++High) {
1383     SDValue &Output = High ? Hi : Lo;
1384
1385     // Build a shuffle mask for the output, discovering on the fly which
1386     // input vectors to use as shuffle operands (recorded in InputUsed).
1387     // If building a suitable shuffle vector proves too hard, then bail
1388     // out with useBuildVector set.
1389     unsigned InputUsed[2] = { -1U, -1U }; // Not yet discovered.
1390     unsigned FirstMaskIdx = High * NewElts;
1391     bool useBuildVector = false;
1392     for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
1393       // The mask element.  This indexes into the input.
1394       int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
1395
1396       // The input vector this mask element indexes into.
1397       unsigned Input = (unsigned)Idx / NewElts;
1398
1399       if (Input >= array_lengthof(Inputs)) {
1400         // The mask element does not index into any input vector.
1401         Ops.push_back(-1);
1402         continue;
1403       }
1404
1405       // Turn the index into an offset from the start of the input vector.
1406       Idx -= Input * NewElts;
1407
1408       // Find or create a shuffle vector operand to hold this input.
1409       unsigned OpNo;
1410       for (OpNo = 0; OpNo < array_lengthof(InputUsed); ++OpNo) {
1411         if (InputUsed[OpNo] == Input) {
1412           // This input vector is already an operand.
1413           break;
1414         } else if (InputUsed[OpNo] == -1U) {
1415           // Create a new operand for this input vector.
1416           InputUsed[OpNo] = Input;
1417           break;
1418         }
1419       }
1420
1421       if (OpNo >= array_lengthof(InputUsed)) {
1422         // More than two input vectors used!  Give up on trying to create a
1423         // shuffle vector.  Insert all elements into a BUILD_VECTOR instead.
1424         useBuildVector = true;
1425         break;
1426       }
1427
1428       // Add the mask index for the new shuffle vector.
1429       Ops.push_back(Idx + OpNo * NewElts);
1430     }
1431
1432     if (useBuildVector) {
1433       EVT EltVT = NewVT.getVectorElementType();
1434       SmallVector<SDValue, 16> SVOps;
1435
1436       // Extract the input elements by hand.
1437       for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) {
1438         // The mask element.  This indexes into the input.
1439         int Idx = N->getMaskElt(FirstMaskIdx + MaskOffset);
1440
1441         // The input vector this mask element indexes into.
1442         unsigned Input = (unsigned)Idx / NewElts;
1443
1444         if (Input >= array_lengthof(Inputs)) {
1445           // The mask element is "undef" or indexes off the end of the input.
1446           SVOps.push_back(DAG.getUNDEF(EltVT));
1447           continue;
1448         }
1449
1450         // Turn the index into an offset from the start of the input vector.
1451         Idx -= Input * NewElts;
1452
1453         // Extract the vector element by hand.
1454         SVOps.push_back(DAG.getNode(
1455             ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Inputs[Input],
1456             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout()))));
1457       }
1458
1459       // Construct the Lo/Hi output using a BUILD_VECTOR.
1460       Output = DAG.getBuildVector(NewVT, dl, SVOps);
1461     } else if (InputUsed[0] == -1U) {
1462       // No input vectors were used!  The result is undefined.
1463       Output = DAG.getUNDEF(NewVT);
1464     } else {
1465       SDValue Op0 = Inputs[InputUsed[0]];
1466       // If only one input was used, use an undefined vector for the other.
1467       SDValue Op1 = InputUsed[1] == -1U ?
1468         DAG.getUNDEF(NewVT) : Inputs[InputUsed[1]];
1469       // At least one input vector was used.  Create a new shuffle vector.
1470       Output =  DAG.getVectorShuffle(NewVT, dl, Op0, Op1, Ops);
1471     }
1472
1473     Ops.clear();
1474   }
1475 }
1476
1477
1478 //===----------------------------------------------------------------------===//
1479 //  Operand Vector Splitting
1480 //===----------------------------------------------------------------------===//
1481
1482 /// This method is called when the specified operand of the specified node is
1483 /// found to need vector splitting. At this point, all of the result types of
1484 /// the node are known to be legal, but other operands of the node may need
1485 /// legalization as well as the specified one.
1486 bool DAGTypeLegalizer::SplitVectorOperand(SDNode *N, unsigned OpNo) {
1487   DEBUG(dbgs() << "Split node operand: ";
1488         N->dump(&DAG);
1489         dbgs() << "\n");
1490   SDValue Res = SDValue();
1491
1492   // See if the target wants to custom split this node.
1493   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
1494     return false;
1495
1496   if (!Res.getNode()) {
1497     switch (N->getOpcode()) {
1498     default:
1499 #ifndef NDEBUG
1500       dbgs() << "SplitVectorOperand Op #" << OpNo << ": ";
1501       N->dump(&DAG);
1502       dbgs() << "\n";
1503 #endif
1504       report_fatal_error("Do not know how to split this operator's "
1505                          "operand!\n");
1506
1507     case ISD::SETCC:             Res = SplitVecOp_VSETCC(N); break;
1508     case ISD::BITCAST:           Res = SplitVecOp_BITCAST(N); break;
1509     case ISD::EXTRACT_SUBVECTOR: Res = SplitVecOp_EXTRACT_SUBVECTOR(N); break;
1510     case ISD::EXTRACT_VECTOR_ELT:Res = SplitVecOp_EXTRACT_VECTOR_ELT(N); break;
1511     case ISD::CONCAT_VECTORS:    Res = SplitVecOp_CONCAT_VECTORS(N); break;
1512     case ISD::TRUNCATE:
1513       Res = SplitVecOp_TruncateHelper(N);
1514       break;
1515     case ISD::FP_ROUND:          Res = SplitVecOp_FP_ROUND(N); break;
1516     case ISD::FCOPYSIGN:         Res = SplitVecOp_FCOPYSIGN(N); break;
1517     case ISD::STORE:
1518       Res = SplitVecOp_STORE(cast<StoreSDNode>(N), OpNo);
1519       break;
1520     case ISD::MSTORE:
1521       Res = SplitVecOp_MSTORE(cast<MaskedStoreSDNode>(N), OpNo);
1522       break;
1523     case ISD::MSCATTER:
1524       Res = SplitVecOp_MSCATTER(cast<MaskedScatterSDNode>(N), OpNo);
1525       break;
1526     case ISD::MGATHER:
1527       Res = SplitVecOp_MGATHER(cast<MaskedGatherSDNode>(N), OpNo);
1528       break;
1529     case ISD::VSELECT:
1530       Res = SplitVecOp_VSELECT(N, OpNo);
1531       break;
1532     case ISD::FP_TO_SINT:
1533     case ISD::FP_TO_UINT:
1534       if (N->getValueType(0).bitsLT(N->getOperand(0)->getValueType(0)))
1535         Res = SplitVecOp_TruncateHelper(N);
1536       else
1537         Res = SplitVecOp_UnaryOp(N);
1538       break;
1539     case ISD::SINT_TO_FP:
1540     case ISD::UINT_TO_FP:
1541       if (N->getValueType(0).bitsLT(N->getOperand(0)->getValueType(0)))
1542         Res = SplitVecOp_TruncateHelper(N);
1543       else
1544         Res = SplitVecOp_UnaryOp(N);
1545       break;
1546     case ISD::CTTZ:
1547     case ISD::CTLZ:
1548     case ISD::CTPOP:
1549     case ISD::FP_EXTEND:
1550     case ISD::SIGN_EXTEND:
1551     case ISD::ZERO_EXTEND:
1552     case ISD::ANY_EXTEND:
1553     case ISD::FTRUNC:
1554     case ISD::FCANONICALIZE:
1555       Res = SplitVecOp_UnaryOp(N);
1556       break;
1557
1558     case ISD::ANY_EXTEND_VECTOR_INREG:
1559     case ISD::SIGN_EXTEND_VECTOR_INREG:
1560     case ISD::ZERO_EXTEND_VECTOR_INREG:
1561       Res = SplitVecOp_ExtVecInRegOp(N);
1562       break;
1563
1564     case ISD::VECREDUCE_FADD:
1565     case ISD::VECREDUCE_FMUL:
1566     case ISD::VECREDUCE_ADD:
1567     case ISD::VECREDUCE_MUL:
1568     case ISD::VECREDUCE_AND:
1569     case ISD::VECREDUCE_OR:
1570     case ISD::VECREDUCE_XOR:
1571     case ISD::VECREDUCE_SMAX:
1572     case ISD::VECREDUCE_SMIN:
1573     case ISD::VECREDUCE_UMAX:
1574     case ISD::VECREDUCE_UMIN:
1575     case ISD::VECREDUCE_FMAX:
1576     case ISD::VECREDUCE_FMIN:
1577       Res = SplitVecOp_VECREDUCE(N, OpNo);
1578       break;
1579     }
1580   }
1581
1582   // If the result is null, the sub-method took care of registering results etc.
1583   if (!Res.getNode()) return false;
1584
1585   // If the result is N, the sub-method updated N in place.  Tell the legalizer
1586   // core about this.
1587   if (Res.getNode() == N)
1588     return true;
1589
1590   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1591          "Invalid operand expansion");
1592
1593   ReplaceValueWith(SDValue(N, 0), Res);
1594   return false;
1595 }
1596
1597 SDValue DAGTypeLegalizer::SplitVecOp_VSELECT(SDNode *N, unsigned OpNo) {
1598   // The only possibility for an illegal operand is the mask, since result type
1599   // legalization would have handled this node already otherwise.
1600   assert(OpNo == 0 && "Illegal operand must be mask");
1601
1602   SDValue Mask = N->getOperand(0);
1603   SDValue Src0 = N->getOperand(1);
1604   SDValue Src1 = N->getOperand(2);
1605   EVT Src0VT = Src0.getValueType();
1606   SDLoc DL(N);
1607   assert(Mask.getValueType().isVector() && "VSELECT without a vector mask?");
1608
1609   SDValue Lo, Hi;
1610   GetSplitVector(N->getOperand(0), Lo, Hi);
1611   assert(Lo.getValueType() == Hi.getValueType() &&
1612          "Lo and Hi have differing types");
1613
1614   EVT LoOpVT, HiOpVT;
1615   std::tie(LoOpVT, HiOpVT) = DAG.GetSplitDestVTs(Src0VT);
1616   assert(LoOpVT == HiOpVT && "Asymmetric vector split?");
1617
1618   SDValue LoOp0, HiOp0, LoOp1, HiOp1, LoMask, HiMask;
1619   std::tie(LoOp0, HiOp0) = DAG.SplitVector(Src0, DL);
1620   std::tie(LoOp1, HiOp1) = DAG.SplitVector(Src1, DL);
1621   std::tie(LoMask, HiMask) = DAG.SplitVector(Mask, DL);
1622
1623   SDValue LoSelect =
1624     DAG.getNode(ISD::VSELECT, DL, LoOpVT, LoMask, LoOp0, LoOp1);
1625   SDValue HiSelect =
1626     DAG.getNode(ISD::VSELECT, DL, HiOpVT, HiMask, HiOp0, HiOp1);
1627
1628   return DAG.getNode(ISD::CONCAT_VECTORS, DL, Src0VT, LoSelect, HiSelect);
1629 }
1630
1631 SDValue DAGTypeLegalizer::SplitVecOp_VECREDUCE(SDNode *N, unsigned OpNo) {
1632   EVT ResVT = N->getValueType(0);
1633   SDValue Lo, Hi;
1634   SDLoc dl(N);
1635
1636   SDValue VecOp = N->getOperand(OpNo);
1637   EVT VecVT = VecOp.getValueType();
1638   assert(VecVT.isVector() && "Can only split reduce vector operand");
1639   GetSplitVector(VecOp, Lo, Hi);
1640   EVT LoOpVT, HiOpVT;
1641   std::tie(LoOpVT, HiOpVT) = DAG.GetSplitDestVTs(VecVT);
1642
1643   bool NoNaN = N->getFlags().hasNoNaNs();
1644   unsigned CombineOpc = 0;
1645   switch (N->getOpcode()) {
1646   case ISD::VECREDUCE_FADD: CombineOpc = ISD::FADD; break;
1647   case ISD::VECREDUCE_FMUL: CombineOpc = ISD::FMUL; break;
1648   case ISD::VECREDUCE_ADD:  CombineOpc = ISD::ADD; break;
1649   case ISD::VECREDUCE_MUL:  CombineOpc = ISD::MUL; break;
1650   case ISD::VECREDUCE_AND:  CombineOpc = ISD::AND; break;
1651   case ISD::VECREDUCE_OR:   CombineOpc = ISD::OR; break;
1652   case ISD::VECREDUCE_XOR:  CombineOpc = ISD::XOR; break;
1653   case ISD::VECREDUCE_SMAX: CombineOpc = ISD::SMAX; break;
1654   case ISD::VECREDUCE_SMIN: CombineOpc = ISD::SMIN; break;
1655   case ISD::VECREDUCE_UMAX: CombineOpc = ISD::UMAX; break;
1656   case ISD::VECREDUCE_UMIN: CombineOpc = ISD::UMIN; break;
1657   case ISD::VECREDUCE_FMAX:
1658     CombineOpc = NoNaN ? ISD::FMAXNUM : ISD::FMAXNAN;
1659     break;
1660   case ISD::VECREDUCE_FMIN:
1661     CombineOpc = NoNaN ? ISD::FMINNUM : ISD::FMINNAN;
1662     break;
1663   default:
1664     llvm_unreachable("Unexpected reduce ISD node");
1665   }
1666
1667   // Use the appropriate scalar instruction on the split subvectors before
1668   // reducing the now partially reduced smaller vector.
1669   SDValue Partial = DAG.getNode(CombineOpc, dl, LoOpVT, Lo, Hi);
1670   return DAG.getNode(N->getOpcode(), dl, ResVT, Partial);
1671 }
1672
1673 SDValue DAGTypeLegalizer::SplitVecOp_UnaryOp(SDNode *N) {
1674   // The result has a legal vector type, but the input needs splitting.
1675   EVT ResVT = N->getValueType(0);
1676   SDValue Lo, Hi;
1677   SDLoc dl(N);
1678   GetSplitVector(N->getOperand(0), Lo, Hi);
1679   EVT InVT = Lo.getValueType();
1680
1681   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
1682                                InVT.getVectorNumElements());
1683
1684   Lo = DAG.getNode(N->getOpcode(), dl, OutVT, Lo);
1685   Hi = DAG.getNode(N->getOpcode(), dl, OutVT, Hi);
1686
1687   return DAG.getNode(ISD::CONCAT_VECTORS, dl, ResVT, Lo, Hi);
1688 }
1689
1690 SDValue DAGTypeLegalizer::SplitVecOp_BITCAST(SDNode *N) {
1691   // For example, i64 = BITCAST v4i16 on alpha.  Typically the vector will
1692   // end up being split all the way down to individual components.  Convert the
1693   // split pieces into integers and reassemble.
1694   SDValue Lo, Hi;
1695   GetSplitVector(N->getOperand(0), Lo, Hi);
1696   Lo = BitConvertToInteger(Lo);
1697   Hi = BitConvertToInteger(Hi);
1698
1699   if (DAG.getDataLayout().isBigEndian())
1700     std::swap(Lo, Hi);
1701
1702   return DAG.getNode(ISD::BITCAST, SDLoc(N), N->getValueType(0),
1703                      JoinIntegers(Lo, Hi));
1704 }
1705
1706 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
1707   // We know that the extracted result type is legal.
1708   EVT SubVT = N->getValueType(0);
1709   SDValue Idx = N->getOperand(1);
1710   SDLoc dl(N);
1711   SDValue Lo, Hi;
1712   GetSplitVector(N->getOperand(0), Lo, Hi);
1713
1714   uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1715   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1716
1717   if (IdxVal < LoElts) {
1718     assert(IdxVal + SubVT.getVectorNumElements() <= LoElts &&
1719            "Extracted subvector crosses vector split!");
1720     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Lo, Idx);
1721   } else {
1722     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SubVT, Hi,
1723                        DAG.getConstant(IdxVal - LoElts, dl,
1724                                        Idx.getValueType()));
1725   }
1726 }
1727
1728 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
1729   SDValue Vec = N->getOperand(0);
1730   SDValue Idx = N->getOperand(1);
1731   EVT VecVT = Vec.getValueType();
1732
1733   if (isa<ConstantSDNode>(Idx)) {
1734     uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
1735     assert(IdxVal < VecVT.getVectorNumElements() && "Invalid vector index!");
1736
1737     SDValue Lo, Hi;
1738     GetSplitVector(Vec, Lo, Hi);
1739
1740     uint64_t LoElts = Lo.getValueType().getVectorNumElements();
1741
1742     if (IdxVal < LoElts)
1743       return SDValue(DAG.UpdateNodeOperands(N, Lo, Idx), 0);
1744     return SDValue(DAG.UpdateNodeOperands(N, Hi,
1745                                   DAG.getConstant(IdxVal - LoElts, SDLoc(N),
1746                                                   Idx.getValueType())), 0);
1747   }
1748
1749   // See if the target wants to custom expand this node.
1750   if (CustomLowerNode(N, N->getValueType(0), true))
1751     return SDValue();
1752
1753   // Make the vector elements byte-addressable if they aren't already.
1754   SDLoc dl(N);
1755   EVT EltVT = VecVT.getVectorElementType();
1756   if (EltVT.getSizeInBits() < 8) {
1757     SmallVector<SDValue, 4> ElementOps;
1758     for (unsigned i = 0; i < VecVT.getVectorNumElements(); ++i) {
1759       ElementOps.push_back(DAG.getAnyExtOrTrunc(
1760           DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Vec,
1761                       DAG.getConstant(i, dl, MVT::i8)),
1762           dl, MVT::i8));
1763     }
1764
1765     EltVT = MVT::i8;
1766     VecVT = EVT::getVectorVT(*DAG.getContext(), EltVT,
1767                              VecVT.getVectorNumElements());
1768     Vec = DAG.getBuildVector(VecVT, dl, ElementOps);
1769   }
1770
1771   // Store the vector to the stack.
1772   SDValue StackPtr = DAG.CreateStackTemporary(VecVT);
1773   SDValue Store =
1774       DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, MachinePointerInfo());
1775
1776   // Load back the required element.
1777   StackPtr = TLI.getVectorElementPointer(DAG, StackPtr, VecVT, Idx);
1778   return DAG.getExtLoad(ISD::EXTLOAD, dl, N->getValueType(0), Store, StackPtr,
1779                         MachinePointerInfo(), EltVT);
1780 }
1781
1782 SDValue DAGTypeLegalizer::SplitVecOp_ExtVecInRegOp(SDNode *N) {
1783   SDValue Lo, Hi;
1784
1785   // *_EXTEND_VECTOR_INREG only reference the lower half of the input, so
1786   // splitting the result has the same effect as splitting the input operand.
1787   SplitVecRes_ExtVecInRegOp(N, Lo, Hi);
1788
1789   return DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(N), N->getValueType(0), Lo, Hi);
1790 }
1791
1792 SDValue DAGTypeLegalizer::SplitVecOp_MGATHER(MaskedGatherSDNode *MGT,
1793                                              unsigned OpNo) {
1794   EVT LoVT, HiVT;
1795   SDLoc dl(MGT);
1796   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(MGT->getValueType(0));
1797
1798   SDValue Ch = MGT->getChain();
1799   SDValue Ptr = MGT->getBasePtr();
1800   SDValue Index = MGT->getIndex();
1801   SDValue Mask = MGT->getMask();
1802   SDValue Src0 = MGT->getValue();
1803   unsigned Alignment = MGT->getOriginalAlignment();
1804
1805   SDValue MaskLo, MaskHi;
1806   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1807     // Split Mask operand
1808     GetSplitVector(Mask, MaskLo, MaskHi);
1809   else
1810     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, dl);
1811
1812   EVT MemoryVT = MGT->getMemoryVT();
1813   EVT LoMemVT, HiMemVT;
1814   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1815
1816   SDValue Src0Lo, Src0Hi;
1817   if (getTypeAction(Src0.getValueType()) == TargetLowering::TypeSplitVector)
1818     GetSplitVector(Src0, Src0Lo, Src0Hi);
1819   else
1820     std::tie(Src0Lo, Src0Hi) = DAG.SplitVector(Src0, dl);
1821
1822   SDValue IndexHi, IndexLo;
1823   if (getTypeAction(Index.getValueType()) == TargetLowering::TypeSplitVector)
1824     GetSplitVector(Index, IndexLo, IndexHi);
1825   else
1826     std::tie(IndexLo, IndexHi) = DAG.SplitVector(Index, dl);
1827
1828   MachineMemOperand *MMO = DAG.getMachineFunction().
1829     getMachineMemOperand(MGT->getPointerInfo(),
1830                          MachineMemOperand::MOLoad,  LoMemVT.getStoreSize(),
1831                          Alignment, MGT->getAAInfo(), MGT->getRanges());
1832
1833   SDValue OpsLo[] = {Ch, Src0Lo, MaskLo, Ptr, IndexLo};
1834   SDValue Lo = DAG.getMaskedGather(DAG.getVTList(LoVT, MVT::Other), LoVT, dl,
1835                                    OpsLo, MMO);
1836
1837   MMO = DAG.getMachineFunction().
1838     getMachineMemOperand(MGT->getPointerInfo(),
1839                          MachineMemOperand::MOLoad,  HiMemVT.getStoreSize(),
1840                          Alignment, MGT->getAAInfo(),
1841                          MGT->getRanges());
1842
1843   SDValue OpsHi[] = {Ch, Src0Hi, MaskHi, Ptr, IndexHi};
1844   SDValue Hi = DAG.getMaskedGather(DAG.getVTList(HiVT, MVT::Other), HiVT, dl,
1845                                    OpsHi, MMO);
1846
1847   // Build a factor node to remember that this load is independent of the
1848   // other one.
1849   Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1850                    Hi.getValue(1));
1851
1852   // Legalize the chain result - switch anything that used the old chain to
1853   // use the new one.
1854   ReplaceValueWith(SDValue(MGT, 1), Ch);
1855
1856   SDValue Res = DAG.getNode(ISD::CONCAT_VECTORS, dl, MGT->getValueType(0), Lo,
1857                             Hi);
1858   ReplaceValueWith(SDValue(MGT, 0), Res);
1859   return SDValue();
1860 }
1861
1862 SDValue DAGTypeLegalizer::SplitVecOp_MSTORE(MaskedStoreSDNode *N,
1863                                             unsigned OpNo) {
1864   SDValue Ch  = N->getChain();
1865   SDValue Ptr = N->getBasePtr();
1866   SDValue Mask = N->getMask();
1867   SDValue Data = N->getValue();
1868   EVT MemoryVT = N->getMemoryVT();
1869   unsigned Alignment = N->getOriginalAlignment();
1870   SDLoc DL(N);
1871
1872   EVT LoMemVT, HiMemVT;
1873   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1874
1875   SDValue DataLo, DataHi;
1876   if (getTypeAction(Data.getValueType()) == TargetLowering::TypeSplitVector)
1877     // Split Data operand
1878     GetSplitVector(Data, DataLo, DataHi);
1879   else
1880     std::tie(DataLo, DataHi) = DAG.SplitVector(Data, DL);
1881
1882   SDValue MaskLo, MaskHi;
1883   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1884     // Split Mask operand
1885     GetSplitVector(Mask, MaskLo, MaskHi);
1886   else
1887     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, DL);
1888
1889   MaskLo = PromoteTargetBoolean(MaskLo, DataLo.getValueType());
1890   MaskHi = PromoteTargetBoolean(MaskHi, DataHi.getValueType());
1891
1892   // if Alignment is equal to the vector size,
1893   // take the half of it for the second part
1894   unsigned SecondHalfAlignment =
1895     (Alignment == Data->getValueType(0).getSizeInBits()/8) ?
1896        Alignment/2 : Alignment;
1897
1898   SDValue Lo, Hi;
1899   MachineMemOperand *MMO = DAG.getMachineFunction().
1900     getMachineMemOperand(N->getPointerInfo(),
1901                          MachineMemOperand::MOStore, LoMemVT.getStoreSize(),
1902                          Alignment, N->getAAInfo(), N->getRanges());
1903
1904   Lo = DAG.getMaskedStore(Ch, DL, DataLo, Ptr, MaskLo, LoMemVT, MMO,
1905                           N->isTruncatingStore(),
1906                           N->isCompressingStore());
1907
1908   Ptr = TLI.IncrementMemoryAddress(Ptr, MaskLo, DL, LoMemVT, DAG,
1909                                    N->isCompressingStore());
1910   MMO = DAG.getMachineFunction().
1911     getMachineMemOperand(N->getPointerInfo(),
1912                          MachineMemOperand::MOStore,  HiMemVT.getStoreSize(),
1913                          SecondHalfAlignment, N->getAAInfo(), N->getRanges());
1914
1915   Hi = DAG.getMaskedStore(Ch, DL, DataHi, Ptr, MaskHi, HiMemVT, MMO,
1916                           N->isTruncatingStore(), N->isCompressingStore());
1917
1918   // Build a factor node to remember that this store is independent of the
1919   // other one.
1920   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
1921 }
1922
1923 SDValue DAGTypeLegalizer::SplitVecOp_MSCATTER(MaskedScatterSDNode *N,
1924                                               unsigned OpNo) {
1925   SDValue Ch  = N->getChain();
1926   SDValue Ptr = N->getBasePtr();
1927   SDValue Mask = N->getMask();
1928   SDValue Index = N->getIndex();
1929   SDValue Data = N->getValue();
1930   EVT MemoryVT = N->getMemoryVT();
1931   unsigned Alignment = N->getOriginalAlignment();
1932   SDLoc DL(N);
1933
1934   // Split all operands
1935   EVT LoMemVT, HiMemVT;
1936   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1937
1938   SDValue DataLo, DataHi;
1939   if (getTypeAction(Data.getValueType()) == TargetLowering::TypeSplitVector)
1940     // Split Data operand
1941     GetSplitVector(Data, DataLo, DataHi);
1942   else
1943     std::tie(DataLo, DataHi) = DAG.SplitVector(Data, DL);
1944
1945   SDValue MaskLo, MaskHi;
1946   if (getTypeAction(Mask.getValueType()) == TargetLowering::TypeSplitVector)
1947     // Split Mask operand
1948     GetSplitVector(Mask, MaskLo, MaskHi);
1949   else
1950     std::tie(MaskLo, MaskHi) = DAG.SplitVector(Mask, DL);
1951
1952   SDValue IndexHi, IndexLo;
1953   if (getTypeAction(Index.getValueType()) == TargetLowering::TypeSplitVector)
1954     GetSplitVector(Index, IndexLo, IndexHi);
1955   else
1956     std::tie(IndexLo, IndexHi) = DAG.SplitVector(Index, DL);
1957
1958   SDValue Lo, Hi;
1959   MachineMemOperand *MMO = DAG.getMachineFunction().
1960     getMachineMemOperand(N->getPointerInfo(),
1961                          MachineMemOperand::MOStore, LoMemVT.getStoreSize(),
1962                          Alignment, N->getAAInfo(), N->getRanges());
1963
1964   SDValue OpsLo[] = {Ch, DataLo, MaskLo, Ptr, IndexLo};
1965   Lo = DAG.getMaskedScatter(DAG.getVTList(MVT::Other), DataLo.getValueType(),
1966                             DL, OpsLo, MMO);
1967
1968   MMO = DAG.getMachineFunction().
1969     getMachineMemOperand(N->getPointerInfo(),
1970                          MachineMemOperand::MOStore,  HiMemVT.getStoreSize(),
1971                          Alignment, N->getAAInfo(), N->getRanges());
1972
1973   SDValue OpsHi[] = {Ch, DataHi, MaskHi, Ptr, IndexHi};
1974   Hi = DAG.getMaskedScatter(DAG.getVTList(MVT::Other), DataHi.getValueType(),
1975                             DL, OpsHi, MMO);
1976
1977   // Build a factor node to remember that this store is independent of the
1978   // other one.
1979   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
1980 }
1981
1982 SDValue DAGTypeLegalizer::SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo) {
1983   assert(N->isUnindexed() && "Indexed store of vector?");
1984   assert(OpNo == 1 && "Can only split the stored value");
1985   SDLoc DL(N);
1986
1987   bool isTruncating = N->isTruncatingStore();
1988   SDValue Ch  = N->getChain();
1989   SDValue Ptr = N->getBasePtr();
1990   EVT MemoryVT = N->getMemoryVT();
1991   unsigned Alignment = N->getOriginalAlignment();
1992   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
1993   AAMDNodes AAInfo = N->getAAInfo();
1994   SDValue Lo, Hi;
1995   GetSplitVector(N->getOperand(1), Lo, Hi);
1996
1997   EVT LoMemVT, HiMemVT;
1998   std::tie(LoMemVT, HiMemVT) = DAG.GetSplitDestVTs(MemoryVT);
1999
2000   unsigned IncrementSize = LoMemVT.getSizeInBits()/8;
2001
2002   if (isTruncating)
2003     Lo = DAG.getTruncStore(Ch, DL, Lo, Ptr, N->getPointerInfo(), LoMemVT,
2004                            Alignment, MMOFlags, AAInfo);
2005   else
2006     Lo = DAG.getStore(Ch, DL, Lo, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
2007                       AAInfo);
2008
2009   // Increment the pointer to the other half.
2010   Ptr = DAG.getNode(ISD::ADD, DL, Ptr.getValueType(), Ptr,
2011                     DAG.getConstant(IncrementSize, DL, Ptr.getValueType()));
2012
2013   if (isTruncating)
2014     Hi = DAG.getTruncStore(Ch, DL, Hi, Ptr,
2015                            N->getPointerInfo().getWithOffset(IncrementSize),
2016                            HiMemVT, Alignment, MMOFlags, AAInfo);
2017   else
2018     Hi = DAG.getStore(Ch, DL, Hi, Ptr,
2019                       N->getPointerInfo().getWithOffset(IncrementSize),
2020                       Alignment, MMOFlags, AAInfo);
2021
2022   return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Lo, Hi);
2023 }
2024
2025 SDValue DAGTypeLegalizer::SplitVecOp_CONCAT_VECTORS(SDNode *N) {
2026   SDLoc DL(N);
2027
2028   // The input operands all must have the same type, and we know the result
2029   // type is valid.  Convert this to a buildvector which extracts all the
2030   // input elements.
2031   // TODO: If the input elements are power-two vectors, we could convert this to
2032   // a new CONCAT_VECTORS node with elements that are half-wide.
2033   SmallVector<SDValue, 32> Elts;
2034   EVT EltVT = N->getValueType(0).getVectorElementType();
2035   for (const SDValue &Op : N->op_values()) {
2036     for (unsigned i = 0, e = Op.getValueType().getVectorNumElements();
2037          i != e; ++i) {
2038       Elts.push_back(DAG.getNode(
2039           ISD::EXTRACT_VECTOR_ELT, DL, EltVT, Op,
2040           DAG.getConstant(i, DL, TLI.getVectorIdxTy(DAG.getDataLayout()))));
2041     }
2042   }
2043
2044   return DAG.getBuildVector(N->getValueType(0), DL, Elts);
2045 }
2046
2047 SDValue DAGTypeLegalizer::SplitVecOp_TruncateHelper(SDNode *N) {
2048   // The result type is legal, but the input type is illegal.  If splitting
2049   // ends up with the result type of each half still being legal, just
2050   // do that.  If, however, that would result in an illegal result type,
2051   // we can try to get more clever with power-two vectors. Specifically,
2052   // split the input type, but also widen the result element size, then
2053   // concatenate the halves and truncate again.  For example, consider a target
2054   // where v8i8 is legal and v8i32 is not (ARM, which doesn't have 256-bit
2055   // vectors). To perform a "%res = v8i8 trunc v8i32 %in" we do:
2056   //   %inlo = v4i32 extract_subvector %in, 0
2057   //   %inhi = v4i32 extract_subvector %in, 4
2058   //   %lo16 = v4i16 trunc v4i32 %inlo
2059   //   %hi16 = v4i16 trunc v4i32 %inhi
2060   //   %in16 = v8i16 concat_vectors v4i16 %lo16, v4i16 %hi16
2061   //   %res = v8i8 trunc v8i16 %in16
2062   //
2063   // Without this transform, the original truncate would end up being
2064   // scalarized, which is pretty much always a last resort.
2065   SDValue InVec = N->getOperand(0);
2066   EVT InVT = InVec->getValueType(0);
2067   EVT OutVT = N->getValueType(0);
2068   unsigned NumElements = OutVT.getVectorNumElements();
2069   bool IsFloat = OutVT.isFloatingPoint();
2070
2071   // Widening should have already made sure this is a power-two vector
2072   // if we're trying to split it at all. assert() that's true, just in case.
2073   assert(!(NumElements & 1) && "Splitting vector, but not in half!");
2074
2075   unsigned InElementSize = InVT.getScalarSizeInBits();
2076   unsigned OutElementSize = OutVT.getScalarSizeInBits();
2077
2078   // If the input elements are only 1/2 the width of the result elements,
2079   // just use the normal splitting. Our trick only work if there's room
2080   // to split more than once.
2081   if (InElementSize <= OutElementSize * 2)
2082     return SplitVecOp_UnaryOp(N);
2083   SDLoc DL(N);
2084
2085   // Extract the halves of the input via extract_subvector.
2086   SDValue InLoVec, InHiVec;
2087   std::tie(InLoVec, InHiVec) = DAG.SplitVector(InVec, DL);
2088   // Truncate them to 1/2 the element size.
2089   EVT HalfElementVT = IsFloat ?
2090     EVT::getFloatingPointVT(InElementSize/2) :
2091     EVT::getIntegerVT(*DAG.getContext(), InElementSize/2);
2092   EVT HalfVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT,
2093                                 NumElements/2);
2094   SDValue HalfLo = DAG.getNode(N->getOpcode(), DL, HalfVT, InLoVec);
2095   SDValue HalfHi = DAG.getNode(N->getOpcode(), DL, HalfVT, InHiVec);
2096   // Concatenate them to get the full intermediate truncation result.
2097   EVT InterVT = EVT::getVectorVT(*DAG.getContext(), HalfElementVT, NumElements);
2098   SDValue InterVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InterVT, HalfLo,
2099                                  HalfHi);
2100   // Now finish up by truncating all the way down to the original result
2101   // type. This should normally be something that ends up being legal directly,
2102   // but in theory if a target has very wide vectors and an annoyingly
2103   // restricted set of legal types, this split can chain to build things up.
2104   return IsFloat
2105              ? DAG.getNode(ISD::FP_ROUND, DL, OutVT, InterVec,
2106                            DAG.getTargetConstant(
2107                                0, DL, TLI.getPointerTy(DAG.getDataLayout())))
2108              : DAG.getNode(ISD::TRUNCATE, DL, OutVT, InterVec);
2109 }
2110
2111 SDValue DAGTypeLegalizer::SplitVecOp_VSETCC(SDNode *N) {
2112   assert(N->getValueType(0).isVector() &&
2113          N->getOperand(0).getValueType().isVector() &&
2114          "Operand types must be vectors");
2115   // The result has a legal vector type, but the input needs splitting.
2116   SDValue Lo0, Hi0, Lo1, Hi1, LoRes, HiRes;
2117   SDLoc DL(N);
2118   GetSplitVector(N->getOperand(0), Lo0, Hi0);
2119   GetSplitVector(N->getOperand(1), Lo1, Hi1);
2120   unsigned PartElements = Lo0.getValueType().getVectorNumElements();
2121   EVT PartResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, PartElements);
2122   EVT WideResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, 2*PartElements);
2123
2124   LoRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Lo0, Lo1, N->getOperand(2));
2125   HiRes = DAG.getNode(ISD::SETCC, DL, PartResVT, Hi0, Hi1, N->getOperand(2));
2126   SDValue Con = DAG.getNode(ISD::CONCAT_VECTORS, DL, WideResVT, LoRes, HiRes);
2127   return PromoteTargetBoolean(Con, N->getValueType(0));
2128 }
2129
2130
2131 SDValue DAGTypeLegalizer::SplitVecOp_FP_ROUND(SDNode *N) {
2132   // The result has a legal vector type, but the input needs splitting.
2133   EVT ResVT = N->getValueType(0);
2134   SDValue Lo, Hi;
2135   SDLoc DL(N);
2136   GetSplitVector(N->getOperand(0), Lo, Hi);
2137   EVT InVT = Lo.getValueType();
2138
2139   EVT OutVT = EVT::getVectorVT(*DAG.getContext(), ResVT.getVectorElementType(),
2140                                InVT.getVectorNumElements());
2141
2142   Lo = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Lo, N->getOperand(1));
2143   Hi = DAG.getNode(ISD::FP_ROUND, DL, OutVT, Hi, N->getOperand(1));
2144
2145   return DAG.getNode(ISD::CONCAT_VECTORS, DL, ResVT, Lo, Hi);
2146 }
2147
2148 SDValue DAGTypeLegalizer::SplitVecOp_FCOPYSIGN(SDNode *N) {
2149   // The result (and the first input) has a legal vector type, but the second
2150   // input needs splitting.
2151   return DAG.UnrollVectorOp(N, N->getValueType(0).getVectorNumElements());
2152 }
2153
2154
2155 //===----------------------------------------------------------------------===//
2156 //  Result Vector Widening
2157 //===----------------------------------------------------------------------===//
2158
2159 void DAGTypeLegalizer::WidenVectorResult(SDNode *N, unsigned ResNo) {
2160   DEBUG(dbgs() << "Widen node result " << ResNo << ": ";
2161         N->dump(&DAG);
2162         dbgs() << "\n");
2163
2164   // See if the target wants to custom widen this node.
2165   if (CustomWidenLowerNode(N, N->getValueType(ResNo)))
2166     return;
2167
2168   SDValue Res = SDValue();
2169   switch (N->getOpcode()) {
2170   default:
2171 #ifndef NDEBUG
2172     dbgs() << "WidenVectorResult #" << ResNo << ": ";
2173     N->dump(&DAG);
2174     dbgs() << "\n";
2175 #endif
2176     llvm_unreachable("Do not know how to widen the result of this operator!");
2177
2178   case ISD::MERGE_VALUES:      Res = WidenVecRes_MERGE_VALUES(N, ResNo); break;
2179   case ISD::BITCAST:           Res = WidenVecRes_BITCAST(N); break;
2180   case ISD::BUILD_VECTOR:      Res = WidenVecRes_BUILD_VECTOR(N); break;
2181   case ISD::CONCAT_VECTORS:    Res = WidenVecRes_CONCAT_VECTORS(N); break;
2182   case ISD::EXTRACT_SUBVECTOR: Res = WidenVecRes_EXTRACT_SUBVECTOR(N); break;
2183   case ISD::FP_ROUND_INREG:    Res = WidenVecRes_InregOp(N); break;
2184   case ISD::INSERT_VECTOR_ELT: Res = WidenVecRes_INSERT_VECTOR_ELT(N); break;
2185   case ISD::LOAD:              Res = WidenVecRes_LOAD(N); break;
2186   case ISD::SCALAR_TO_VECTOR:  Res = WidenVecRes_SCALAR_TO_VECTOR(N); break;
2187   case ISD::SIGN_EXTEND_INREG: Res = WidenVecRes_InregOp(N); break;
2188   case ISD::VSELECT:
2189   case ISD::SELECT:            Res = WidenVecRes_SELECT(N); break;
2190   case ISD::SELECT_CC:         Res = WidenVecRes_SELECT_CC(N); break;
2191   case ISD::SETCC:             Res = WidenVecRes_SETCC(N); break;
2192   case ISD::UNDEF:             Res = WidenVecRes_UNDEF(N); break;
2193   case ISD::VECTOR_SHUFFLE:
2194     Res = WidenVecRes_VECTOR_SHUFFLE(cast<ShuffleVectorSDNode>(N));
2195     break;
2196   case ISD::MLOAD:
2197     Res = WidenVecRes_MLOAD(cast<MaskedLoadSDNode>(N));
2198     break;
2199   case ISD::MGATHER:
2200     Res = WidenVecRes_MGATHER(cast<MaskedGatherSDNode>(N));
2201     break;
2202
2203   case ISD::ADD:
2204   case ISD::AND:
2205   case ISD::MUL:
2206   case ISD::MULHS:
2207   case ISD::MULHU:
2208   case ISD::OR:
2209   case ISD::SUB:
2210   case ISD::XOR:
2211   case ISD::FMINNUM:
2212   case ISD::FMAXNUM:
2213   case ISD::FMINNAN:
2214   case ISD::FMAXNAN:
2215   case ISD::SMIN:
2216   case ISD::SMAX:
2217   case ISD::UMIN:
2218   case ISD::UMAX:
2219     Res = WidenVecRes_Binary(N);
2220     break;
2221
2222   case ISD::FADD:
2223   case ISD::FMUL:
2224   case ISD::FPOW:
2225   case ISD::FSUB:
2226   case ISD::FDIV:
2227   case ISD::FREM:
2228   case ISD::SDIV:
2229   case ISD::UDIV:
2230   case ISD::SREM:
2231   case ISD::UREM:
2232     Res = WidenVecRes_BinaryCanTrap(N);
2233     break;
2234
2235   case ISD::FCOPYSIGN:
2236     Res = WidenVecRes_FCOPYSIGN(N);
2237     break;
2238
2239   case ISD::FPOWI:
2240     Res = WidenVecRes_POWI(N);
2241     break;
2242
2243   case ISD::SHL:
2244   case ISD::SRA:
2245   case ISD::SRL:
2246     Res = WidenVecRes_Shift(N);
2247     break;
2248
2249   case ISD::ANY_EXTEND_VECTOR_INREG:
2250   case ISD::SIGN_EXTEND_VECTOR_INREG:
2251   case ISD::ZERO_EXTEND_VECTOR_INREG:
2252     Res = WidenVecRes_EXTEND_VECTOR_INREG(N);
2253     break;
2254
2255   case ISD::ANY_EXTEND:
2256   case ISD::FP_EXTEND:
2257   case ISD::FP_ROUND:
2258   case ISD::FP_TO_SINT:
2259   case ISD::FP_TO_UINT:
2260   case ISD::SIGN_EXTEND:
2261   case ISD::SINT_TO_FP:
2262   case ISD::TRUNCATE:
2263   case ISD::UINT_TO_FP:
2264   case ISD::ZERO_EXTEND:
2265     Res = WidenVecRes_Convert(N);
2266     break;
2267
2268   case ISD::BITREVERSE:
2269   case ISD::BSWAP:
2270   case ISD::CTLZ:
2271   case ISD::CTPOP:
2272   case ISD::CTTZ:
2273   case ISD::FABS:
2274   case ISD::FCEIL:
2275   case ISD::FCOS:
2276   case ISD::FEXP:
2277   case ISD::FEXP2:
2278   case ISD::FFLOOR:
2279   case ISD::FLOG:
2280   case ISD::FLOG10:
2281   case ISD::FLOG2:
2282   case ISD::FNEARBYINT:
2283   case ISD::FNEG:
2284   case ISD::FRINT:
2285   case ISD::FROUND:
2286   case ISD::FSIN:
2287   case ISD::FSQRT:
2288   case ISD::FTRUNC:
2289     Res = WidenVecRes_Unary(N);
2290     break;
2291   case ISD::FMA:
2292     Res = WidenVecRes_Ternary(N);
2293     break;
2294   }
2295
2296   // If Res is null, the sub-method took care of registering the result.
2297   if (Res.getNode())
2298     SetWidenedVector(SDValue(N, ResNo), Res);
2299 }
2300
2301 SDValue DAGTypeLegalizer::WidenVecRes_Ternary(SDNode *N) {
2302   // Ternary op widening.
2303   SDLoc dl(N);
2304   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2305   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2306   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2307   SDValue InOp3 = GetWidenedVector(N->getOperand(2));
2308   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, InOp3);
2309 }
2310
2311 SDValue DAGTypeLegalizer::WidenVecRes_Binary(SDNode *N) {
2312   // Binary op widening.
2313   SDLoc dl(N);
2314   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2315   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2316   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2317   return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, N->getFlags());
2318 }
2319
2320 SDValue DAGTypeLegalizer::WidenVecRes_BinaryCanTrap(SDNode *N) {
2321   // Binary op widening for operations that can trap.
2322   unsigned Opcode = N->getOpcode();
2323   SDLoc dl(N);
2324   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2325   EVT WidenEltVT = WidenVT.getVectorElementType();
2326   EVT VT = WidenVT;
2327   unsigned NumElts =  VT.getVectorNumElements();
2328   const SDNodeFlags Flags = N->getFlags();
2329   while (!TLI.isTypeLegal(VT) && NumElts != 1) {
2330     NumElts = NumElts / 2;
2331     VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
2332   }
2333
2334   if (NumElts != 1 && !TLI.canOpTrap(N->getOpcode(), VT)) {
2335     // Operation doesn't trap so just widen as normal.
2336     SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2337     SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2338     return DAG.getNode(N->getOpcode(), dl, WidenVT, InOp1, InOp2, Flags);
2339   }
2340
2341   // No legal vector version so unroll the vector operation and then widen.
2342   if (NumElts == 1)
2343     return DAG.UnrollVectorOp(N, WidenVT.getVectorNumElements());
2344
2345   // Since the operation can trap, apply operation on the original vector.
2346   EVT MaxVT = VT;
2347   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
2348   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
2349   unsigned CurNumElts = N->getValueType(0).getVectorNumElements();
2350
2351   SmallVector<SDValue, 16> ConcatOps(CurNumElts);
2352   unsigned ConcatEnd = 0;  // Current ConcatOps index.
2353   int Idx = 0;        // Current Idx into input vectors.
2354
2355   // NumElts := greatest legal vector size (at most WidenVT)
2356   // while (orig. vector has unhandled elements) {
2357   //   take munches of size NumElts from the beginning and add to ConcatOps
2358   //   NumElts := next smaller supported vector size or 1
2359   // }
2360   while (CurNumElts != 0) {
2361     while (CurNumElts >= NumElts) {
2362       SDValue EOp1 = DAG.getNode(
2363           ISD::EXTRACT_SUBVECTOR, dl, VT, InOp1,
2364           DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2365       SDValue EOp2 = DAG.getNode(
2366           ISD::EXTRACT_SUBVECTOR, dl, VT, InOp2,
2367           DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2368       ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, VT, EOp1, EOp2, Flags);
2369       Idx += NumElts;
2370       CurNumElts -= NumElts;
2371     }
2372     do {
2373       NumElts = NumElts / 2;
2374       VT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NumElts);
2375     } while (!TLI.isTypeLegal(VT) && NumElts != 1);
2376
2377     if (NumElts == 1) {
2378       for (unsigned i = 0; i != CurNumElts; ++i, ++Idx) {
2379         SDValue EOp1 = DAG.getNode(
2380             ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT, InOp1,
2381             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2382         SDValue EOp2 = DAG.getNode(
2383             ISD::EXTRACT_VECTOR_ELT, dl, WidenEltVT, InOp2,
2384             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2385         ConcatOps[ConcatEnd++] = DAG.getNode(Opcode, dl, WidenEltVT,
2386                                              EOp1, EOp2, Flags);
2387       }
2388       CurNumElts = 0;
2389     }
2390   }
2391
2392   // Check to see if we have a single operation with the widen type.
2393   if (ConcatEnd == 1) {
2394     VT = ConcatOps[0].getValueType();
2395     if (VT == WidenVT)
2396       return ConcatOps[0];
2397   }
2398
2399   // while (Some element of ConcatOps is not of type MaxVT) {
2400   //   From the end of ConcatOps, collect elements of the same type and put
2401   //   them into an op of the next larger supported type
2402   // }
2403   while (ConcatOps[ConcatEnd-1].getValueType() != MaxVT) {
2404     Idx = ConcatEnd - 1;
2405     VT = ConcatOps[Idx--].getValueType();
2406     while (Idx >= 0 && ConcatOps[Idx].getValueType() == VT)
2407       Idx--;
2408
2409     int NextSize = VT.isVector() ? VT.getVectorNumElements() : 1;
2410     EVT NextVT;
2411     do {
2412       NextSize *= 2;
2413       NextVT = EVT::getVectorVT(*DAG.getContext(), WidenEltVT, NextSize);
2414     } while (!TLI.isTypeLegal(NextVT));
2415
2416     if (!VT.isVector()) {
2417       // Scalar type, create an INSERT_VECTOR_ELEMENT of type NextVT
2418       SDValue VecOp = DAG.getUNDEF(NextVT);
2419       unsigned NumToInsert = ConcatEnd - Idx - 1;
2420       for (unsigned i = 0, OpIdx = Idx+1; i < NumToInsert; i++, OpIdx++) {
2421         VecOp = DAG.getNode(
2422             ISD::INSERT_VECTOR_ELT, dl, NextVT, VecOp, ConcatOps[OpIdx],
2423             DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2424       }
2425       ConcatOps[Idx+1] = VecOp;
2426       ConcatEnd = Idx + 2;
2427     } else {
2428       // Vector type, create a CONCAT_VECTORS of type NextVT
2429       SDValue undefVec = DAG.getUNDEF(VT);
2430       unsigned OpsToConcat = NextSize/VT.getVectorNumElements();
2431       SmallVector<SDValue, 16> SubConcatOps(OpsToConcat);
2432       unsigned RealVals = ConcatEnd - Idx - 1;
2433       unsigned SubConcatEnd = 0;
2434       unsigned SubConcatIdx = Idx + 1;
2435       while (SubConcatEnd < RealVals)
2436         SubConcatOps[SubConcatEnd++] = ConcatOps[++Idx];
2437       while (SubConcatEnd < OpsToConcat)
2438         SubConcatOps[SubConcatEnd++] = undefVec;
2439       ConcatOps[SubConcatIdx] = DAG.getNode(ISD::CONCAT_VECTORS, dl,
2440                                             NextVT, SubConcatOps);
2441       ConcatEnd = SubConcatIdx + 1;
2442     }
2443   }
2444
2445   // Check to see if we have a single operation with the widen type.
2446   if (ConcatEnd == 1) {
2447     VT = ConcatOps[0].getValueType();
2448     if (VT == WidenVT)
2449       return ConcatOps[0];
2450   }
2451
2452   // add undefs of size MaxVT until ConcatOps grows to length of WidenVT
2453   unsigned NumOps = WidenVT.getVectorNumElements()/MaxVT.getVectorNumElements();
2454   if (NumOps != ConcatEnd ) {
2455     SDValue UndefVal = DAG.getUNDEF(MaxVT);
2456     for (unsigned j = ConcatEnd; j < NumOps; ++j)
2457       ConcatOps[j] = UndefVal;
2458   }
2459   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
2460                      makeArrayRef(ConcatOps.data(), NumOps));
2461 }
2462
2463 SDValue DAGTypeLegalizer::WidenVecRes_Convert(SDNode *N) {
2464   SDValue InOp = N->getOperand(0);
2465   SDLoc DL(N);
2466
2467   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2468   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2469
2470   EVT InVT = InOp.getValueType();
2471   EVT InEltVT = InVT.getVectorElementType();
2472   EVT InWidenVT = EVT::getVectorVT(*DAG.getContext(), InEltVT, WidenNumElts);
2473
2474   unsigned Opcode = N->getOpcode();
2475   unsigned InVTNumElts = InVT.getVectorNumElements();
2476   const SDNodeFlags Flags = N->getFlags();
2477   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
2478     InOp = GetWidenedVector(N->getOperand(0));
2479     InVT = InOp.getValueType();
2480     InVTNumElts = InVT.getVectorNumElements();
2481     if (InVTNumElts == WidenNumElts) {
2482       if (N->getNumOperands() == 1)
2483         return DAG.getNode(Opcode, DL, WidenVT, InOp);
2484       return DAG.getNode(Opcode, DL, WidenVT, InOp, N->getOperand(1), Flags);
2485     }
2486     if (WidenVT.getSizeInBits() == InVT.getSizeInBits()) {
2487       // If both input and result vector types are of same width, extend
2488       // operations should be done with SIGN/ZERO_EXTEND_VECTOR_INREG, which
2489       // accepts fewer elements in the result than in the input.
2490       if (Opcode == ISD::SIGN_EXTEND)
2491         return DAG.getSignExtendVectorInReg(InOp, DL, WidenVT);
2492       if (Opcode == ISD::ZERO_EXTEND)
2493         return DAG.getZeroExtendVectorInReg(InOp, DL, WidenVT);
2494     }
2495   }
2496
2497   if (TLI.isTypeLegal(InWidenVT)) {
2498     // Because the result and the input are different vector types, widening
2499     // the result could create a legal type but widening the input might make
2500     // it an illegal type that might lead to repeatedly splitting the input
2501     // and then widening it. To avoid this, we widen the input only if
2502     // it results in a legal type.
2503     if (WidenNumElts % InVTNumElts == 0) {
2504       // Widen the input and call convert on the widened input vector.
2505       unsigned NumConcat = WidenNumElts/InVTNumElts;
2506       SmallVector<SDValue, 16> Ops(NumConcat);
2507       Ops[0] = InOp;
2508       SDValue UndefVal = DAG.getUNDEF(InVT);
2509       for (unsigned i = 1; i != NumConcat; ++i)
2510         Ops[i] = UndefVal;
2511       SDValue InVec = DAG.getNode(ISD::CONCAT_VECTORS, DL, InWidenVT, Ops);
2512       if (N->getNumOperands() == 1)
2513         return DAG.getNode(Opcode, DL, WidenVT, InVec);
2514       return DAG.getNode(Opcode, DL, WidenVT, InVec, N->getOperand(1), Flags);
2515     }
2516
2517     if (InVTNumElts % WidenNumElts == 0) {
2518       SDValue InVal = DAG.getNode(
2519           ISD::EXTRACT_SUBVECTOR, DL, InWidenVT, InOp,
2520           DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
2521       // Extract the input and convert the shorten input vector.
2522       if (N->getNumOperands() == 1)
2523         return DAG.getNode(Opcode, DL, WidenVT, InVal);
2524       return DAG.getNode(Opcode, DL, WidenVT, InVal, N->getOperand(1), Flags);
2525     }
2526   }
2527
2528   // Otherwise unroll into some nasty scalar code and rebuild the vector.
2529   SmallVector<SDValue, 16> Ops(WidenNumElts);
2530   EVT EltVT = WidenVT.getVectorElementType();
2531   unsigned MinElts = std::min(InVTNumElts, WidenNumElts);
2532   unsigned i;
2533   for (i=0; i < MinElts; ++i) {
2534     SDValue Val = DAG.getNode(
2535         ISD::EXTRACT_VECTOR_ELT, DL, InEltVT, InOp,
2536         DAG.getConstant(i, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
2537     if (N->getNumOperands() == 1)
2538       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val);
2539     else
2540       Ops[i] = DAG.getNode(Opcode, DL, EltVT, Val, N->getOperand(1), Flags);
2541   }
2542
2543   SDValue UndefVal = DAG.getUNDEF(EltVT);
2544   for (; i < WidenNumElts; ++i)
2545     Ops[i] = UndefVal;
2546
2547   return DAG.getBuildVector(WidenVT, DL, Ops);
2548 }
2549
2550 SDValue DAGTypeLegalizer::WidenVecRes_EXTEND_VECTOR_INREG(SDNode *N) {
2551   unsigned Opcode = N->getOpcode();
2552   SDValue InOp = N->getOperand(0);
2553   SDLoc DL(N);
2554
2555   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2556   EVT WidenSVT = WidenVT.getVectorElementType();
2557   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2558
2559   EVT InVT = InOp.getValueType();
2560   EVT InSVT = InVT.getVectorElementType();
2561   unsigned InVTNumElts = InVT.getVectorNumElements();
2562
2563   if (getTypeAction(InVT) == TargetLowering::TypeWidenVector) {
2564     InOp = GetWidenedVector(InOp);
2565     InVT = InOp.getValueType();
2566     if (InVT.getSizeInBits() == WidenVT.getSizeInBits()) {
2567       switch (Opcode) {
2568       case ISD::ANY_EXTEND_VECTOR_INREG:
2569         return DAG.getAnyExtendVectorInReg(InOp, DL, WidenVT);
2570       case ISD::SIGN_EXTEND_VECTOR_INREG:
2571         return DAG.getSignExtendVectorInReg(InOp, DL, WidenVT);
2572       case ISD::ZERO_EXTEND_VECTOR_INREG:
2573         return DAG.getZeroExtendVectorInReg(InOp, DL, WidenVT);
2574       }
2575     }
2576   }
2577
2578   // Unroll, extend the scalars and rebuild the vector.
2579   SmallVector<SDValue, 16> Ops;
2580   for (unsigned i = 0, e = std::min(InVTNumElts, WidenNumElts); i != e; ++i) {
2581     SDValue Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, InSVT, InOp,
2582       DAG.getConstant(i, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
2583     switch (Opcode) {
2584     case ISD::ANY_EXTEND_VECTOR_INREG:
2585       Val = DAG.getNode(ISD::ANY_EXTEND, DL, WidenSVT, Val);
2586       break;
2587     case ISD::SIGN_EXTEND_VECTOR_INREG:
2588       Val = DAG.getNode(ISD::SIGN_EXTEND, DL, WidenSVT, Val);
2589       break;
2590     case ISD::ZERO_EXTEND_VECTOR_INREG:
2591       Val = DAG.getNode(ISD::ZERO_EXTEND, DL, WidenSVT, Val);
2592       break;
2593     default:
2594       llvm_unreachable("A *_EXTEND_VECTOR_INREG node was expected");
2595     }
2596     Ops.push_back(Val);
2597   }
2598
2599   while (Ops.size() != WidenNumElts)
2600     Ops.push_back(DAG.getUNDEF(WidenSVT));
2601
2602   return DAG.getBuildVector(WidenVT, DL, Ops);
2603 }
2604
2605 SDValue DAGTypeLegalizer::WidenVecRes_FCOPYSIGN(SDNode *N) {
2606   // If this is an FCOPYSIGN with same input types, we can treat it as a
2607   // normal (can trap) binary op.
2608   if (N->getOperand(0).getValueType() == N->getOperand(1).getValueType())
2609     return WidenVecRes_BinaryCanTrap(N);
2610
2611   // If the types are different, fall back to unrolling.
2612   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2613   return DAG.UnrollVectorOp(N, WidenVT.getVectorNumElements());
2614 }
2615
2616 SDValue DAGTypeLegalizer::WidenVecRes_POWI(SDNode *N) {
2617   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2618   SDValue InOp = GetWidenedVector(N->getOperand(0));
2619   SDValue ShOp = N->getOperand(1);
2620   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
2621 }
2622
2623 SDValue DAGTypeLegalizer::WidenVecRes_Shift(SDNode *N) {
2624   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2625   SDValue InOp = GetWidenedVector(N->getOperand(0));
2626   SDValue ShOp = N->getOperand(1);
2627
2628   EVT ShVT = ShOp.getValueType();
2629   if (getTypeAction(ShVT) == TargetLowering::TypeWidenVector) {
2630     ShOp = GetWidenedVector(ShOp);
2631     ShVT = ShOp.getValueType();
2632   }
2633   EVT ShWidenVT = EVT::getVectorVT(*DAG.getContext(),
2634                                    ShVT.getVectorElementType(),
2635                                    WidenVT.getVectorNumElements());
2636   if (ShVT != ShWidenVT)
2637     ShOp = ModifyToType(ShOp, ShWidenVT);
2638
2639   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp, ShOp);
2640 }
2641
2642 SDValue DAGTypeLegalizer::WidenVecRes_Unary(SDNode *N) {
2643   // Unary op widening.
2644   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2645   SDValue InOp = GetWidenedVector(N->getOperand(0));
2646   return DAG.getNode(N->getOpcode(), SDLoc(N), WidenVT, InOp);
2647 }
2648
2649 SDValue DAGTypeLegalizer::WidenVecRes_InregOp(SDNode *N) {
2650   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2651   EVT ExtVT = EVT::getVectorVT(*DAG.getContext(),
2652                                cast<VTSDNode>(N->getOperand(1))->getVT()
2653                                  .getVectorElementType(),
2654                                WidenVT.getVectorNumElements());
2655   SDValue WidenLHS = GetWidenedVector(N->getOperand(0));
2656   return DAG.getNode(N->getOpcode(), SDLoc(N),
2657                      WidenVT, WidenLHS, DAG.getValueType(ExtVT));
2658 }
2659
2660 SDValue DAGTypeLegalizer::WidenVecRes_MERGE_VALUES(SDNode *N, unsigned ResNo) {
2661   SDValue WidenVec = DisintegrateMERGE_VALUES(N, ResNo);
2662   return GetWidenedVector(WidenVec);
2663 }
2664
2665 SDValue DAGTypeLegalizer::WidenVecRes_BITCAST(SDNode *N) {
2666   SDValue InOp = N->getOperand(0);
2667   EVT InVT = InOp.getValueType();
2668   EVT VT = N->getValueType(0);
2669   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2670   SDLoc dl(N);
2671
2672   switch (getTypeAction(InVT)) {
2673   case TargetLowering::TypeLegal:
2674     break;
2675   case TargetLowering::TypePromoteInteger:
2676     // If the incoming type is a vector that is being promoted, then
2677     // we know that the elements are arranged differently and that we
2678     // must perform the conversion using a stack slot.
2679     if (InVT.isVector())
2680       break;
2681
2682     // If the InOp is promoted to the same size, convert it.  Otherwise,
2683     // fall out of the switch and widen the promoted input.
2684     InOp = GetPromotedInteger(InOp);
2685     InVT = InOp.getValueType();
2686     if (WidenVT.bitsEq(InVT))
2687       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
2688     break;
2689   case TargetLowering::TypeSoftenFloat:
2690   case TargetLowering::TypePromoteFloat:
2691   case TargetLowering::TypeExpandInteger:
2692   case TargetLowering::TypeExpandFloat:
2693   case TargetLowering::TypeScalarizeVector:
2694   case TargetLowering::TypeSplitVector:
2695     break;
2696   case TargetLowering::TypeWidenVector:
2697     // If the InOp is widened to the same size, convert it.  Otherwise, fall
2698     // out of the switch and widen the widened input.
2699     InOp = GetWidenedVector(InOp);
2700     InVT = InOp.getValueType();
2701     if (WidenVT.bitsEq(InVT))
2702       // The input widens to the same size. Convert to the widen value.
2703       return DAG.getNode(ISD::BITCAST, dl, WidenVT, InOp);
2704     break;
2705   }
2706
2707   unsigned WidenSize = WidenVT.getSizeInBits();
2708   unsigned InSize = InVT.getSizeInBits();
2709   // x86mmx is not an acceptable vector element type, so don't try.
2710   if (WidenSize % InSize == 0 && InVT != MVT::x86mmx) {
2711     // Determine new input vector type.  The new input vector type will use
2712     // the same element type (if its a vector) or use the input type as a
2713     // vector.  It is the same size as the type to widen to.
2714     EVT NewInVT;
2715     unsigned NewNumElts = WidenSize / InSize;
2716     if (InVT.isVector()) {
2717       EVT InEltVT = InVT.getVectorElementType();
2718       NewInVT = EVT::getVectorVT(*DAG.getContext(), InEltVT,
2719                                  WidenSize / InEltVT.getSizeInBits());
2720     } else {
2721       NewInVT = EVT::getVectorVT(*DAG.getContext(), InVT, NewNumElts);
2722     }
2723
2724     if (TLI.isTypeLegal(NewInVT)) {
2725       // Because the result and the input are different vector types, widening
2726       // the result could create a legal type but widening the input might make
2727       // it an illegal type that might lead to repeatedly splitting the input
2728       // and then widening it. To avoid this, we widen the input only if
2729       // it results in a legal type.
2730       SmallVector<SDValue, 16> Ops(NewNumElts);
2731       SDValue UndefVal = DAG.getUNDEF(InVT);
2732       Ops[0] = InOp;
2733       for (unsigned i = 1; i < NewNumElts; ++i)
2734         Ops[i] = UndefVal;
2735
2736       SDValue NewVec;
2737       if (InVT.isVector())
2738         NewVec = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewInVT, Ops);
2739       else
2740         NewVec = DAG.getBuildVector(NewInVT, dl, Ops);
2741       return DAG.getNode(ISD::BITCAST, dl, WidenVT, NewVec);
2742     }
2743   }
2744
2745   return CreateStackStoreLoad(InOp, WidenVT);
2746 }
2747
2748 SDValue DAGTypeLegalizer::WidenVecRes_BUILD_VECTOR(SDNode *N) {
2749   SDLoc dl(N);
2750   // Build a vector with undefined for the new nodes.
2751   EVT VT = N->getValueType(0);
2752
2753   // Integer BUILD_VECTOR operands may be larger than the node's vector element
2754   // type. The UNDEFs need to have the same type as the existing operands.
2755   EVT EltVT = N->getOperand(0).getValueType();
2756   unsigned NumElts = VT.getVectorNumElements();
2757
2758   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2759   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2760
2761   SmallVector<SDValue, 16> NewOps(N->op_begin(), N->op_end());
2762   assert(WidenNumElts >= NumElts && "Shrinking vector instead of widening!");
2763   NewOps.append(WidenNumElts - NumElts, DAG.getUNDEF(EltVT));
2764
2765   return DAG.getBuildVector(WidenVT, dl, NewOps);
2766 }
2767
2768 SDValue DAGTypeLegalizer::WidenVecRes_CONCAT_VECTORS(SDNode *N) {
2769   EVT InVT = N->getOperand(0).getValueType();
2770   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2771   SDLoc dl(N);
2772   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2773   unsigned NumInElts = InVT.getVectorNumElements();
2774   unsigned NumOperands = N->getNumOperands();
2775
2776   bool InputWidened = false; // Indicates we need to widen the input.
2777   if (getTypeAction(InVT) != TargetLowering::TypeWidenVector) {
2778     if (WidenVT.getVectorNumElements() % InVT.getVectorNumElements() == 0) {
2779       // Add undef vectors to widen to correct length.
2780       unsigned NumConcat = WidenVT.getVectorNumElements() /
2781                            InVT.getVectorNumElements();
2782       SDValue UndefVal = DAG.getUNDEF(InVT);
2783       SmallVector<SDValue, 16> Ops(NumConcat);
2784       for (unsigned i=0; i < NumOperands; ++i)
2785         Ops[i] = N->getOperand(i);
2786       for (unsigned i = NumOperands; i != NumConcat; ++i)
2787         Ops[i] = UndefVal;
2788       return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, Ops);
2789     }
2790   } else {
2791     InputWidened = true;
2792     if (WidenVT == TLI.getTypeToTransformTo(*DAG.getContext(), InVT)) {
2793       // The inputs and the result are widen to the same value.
2794       unsigned i;
2795       for (i=1; i < NumOperands; ++i)
2796         if (!N->getOperand(i).isUndef())
2797           break;
2798
2799       if (i == NumOperands)
2800         // Everything but the first operand is an UNDEF so just return the
2801         // widened first operand.
2802         return GetWidenedVector(N->getOperand(0));
2803
2804       if (NumOperands == 2) {
2805         // Replace concat of two operands with a shuffle.
2806         SmallVector<int, 16> MaskOps(WidenNumElts, -1);
2807         for (unsigned i = 0; i < NumInElts; ++i) {
2808           MaskOps[i] = i;
2809           MaskOps[i + NumInElts] = i + WidenNumElts;
2810         }
2811         return DAG.getVectorShuffle(WidenVT, dl,
2812                                     GetWidenedVector(N->getOperand(0)),
2813                                     GetWidenedVector(N->getOperand(1)),
2814                                     MaskOps);
2815       }
2816     }
2817   }
2818
2819   // Fall back to use extracts and build vector.
2820   EVT EltVT = WidenVT.getVectorElementType();
2821   SmallVector<SDValue, 16> Ops(WidenNumElts);
2822   unsigned Idx = 0;
2823   for (unsigned i=0; i < NumOperands; ++i) {
2824     SDValue InOp = N->getOperand(i);
2825     if (InputWidened)
2826       InOp = GetWidenedVector(InOp);
2827     for (unsigned j=0; j < NumInElts; ++j)
2828       Ops[Idx++] = DAG.getNode(
2829           ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2830           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
2831   }
2832   SDValue UndefVal = DAG.getUNDEF(EltVT);
2833   for (; Idx < WidenNumElts; ++Idx)
2834     Ops[Idx] = UndefVal;
2835   return DAG.getBuildVector(WidenVT, dl, Ops);
2836 }
2837
2838 SDValue DAGTypeLegalizer::WidenVecRes_EXTRACT_SUBVECTOR(SDNode *N) {
2839   EVT      VT = N->getValueType(0);
2840   EVT      WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2841   unsigned WidenNumElts = WidenVT.getVectorNumElements();
2842   SDValue  InOp = N->getOperand(0);
2843   SDValue  Idx  = N->getOperand(1);
2844   SDLoc dl(N);
2845
2846   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
2847     InOp = GetWidenedVector(InOp);
2848
2849   EVT InVT = InOp.getValueType();
2850
2851   // Check if we can just return the input vector after widening.
2852   uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
2853   if (IdxVal == 0 && InVT == WidenVT)
2854     return InOp;
2855
2856   // Check if we can extract from the vector.
2857   unsigned InNumElts = InVT.getVectorNumElements();
2858   if (IdxVal % WidenNumElts == 0 && IdxVal + WidenNumElts < InNumElts)
2859     return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, WidenVT, InOp, Idx);
2860
2861   // We could try widening the input to the right length but for now, extract
2862   // the original elements, fill the rest with undefs and build a vector.
2863   SmallVector<SDValue, 16> Ops(WidenNumElts);
2864   EVT EltVT = VT.getVectorElementType();
2865   unsigned NumElts = VT.getVectorNumElements();
2866   unsigned i;
2867   for (i=0; i < NumElts; ++i)
2868     Ops[i] =
2869         DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
2870                     DAG.getConstant(IdxVal + i, dl,
2871                                     TLI.getVectorIdxTy(DAG.getDataLayout())));
2872
2873   SDValue UndefVal = DAG.getUNDEF(EltVT);
2874   for (; i < WidenNumElts; ++i)
2875     Ops[i] = UndefVal;
2876   return DAG.getBuildVector(WidenVT, dl, Ops);
2877 }
2878
2879 SDValue DAGTypeLegalizer::WidenVecRes_INSERT_VECTOR_ELT(SDNode *N) {
2880   SDValue InOp = GetWidenedVector(N->getOperand(0));
2881   return DAG.getNode(ISD::INSERT_VECTOR_ELT, SDLoc(N),
2882                      InOp.getValueType(), InOp,
2883                      N->getOperand(1), N->getOperand(2));
2884 }
2885
2886 SDValue DAGTypeLegalizer::WidenVecRes_LOAD(SDNode *N) {
2887   LoadSDNode *LD = cast<LoadSDNode>(N);
2888   ISD::LoadExtType ExtType = LD->getExtensionType();
2889
2890   SDValue Result;
2891   SmallVector<SDValue, 16> LdChain;  // Chain for the series of load
2892   if (ExtType != ISD::NON_EXTLOAD)
2893     Result = GenWidenVectorExtLoads(LdChain, LD, ExtType);
2894   else
2895     Result = GenWidenVectorLoads(LdChain, LD);
2896
2897   // If we generate a single load, we can use that for the chain.  Otherwise,
2898   // build a factor node to remember the multiple loads are independent and
2899   // chain to that.
2900   SDValue NewChain;
2901   if (LdChain.size() == 1)
2902     NewChain = LdChain[0];
2903   else
2904     NewChain = DAG.getNode(ISD::TokenFactor, SDLoc(LD), MVT::Other, LdChain);
2905
2906   // Modified the chain - switch anything that used the old chain to use
2907   // the new one.
2908   ReplaceValueWith(SDValue(N, 1), NewChain);
2909
2910   return Result;
2911 }
2912
2913 SDValue DAGTypeLegalizer::WidenVecRes_MLOAD(MaskedLoadSDNode *N) {
2914
2915   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),N->getValueType(0));
2916   SDValue Mask = N->getMask();
2917   EVT MaskVT = Mask.getValueType();
2918   SDValue Src0 = GetWidenedVector(N->getSrc0());
2919   ISD::LoadExtType ExtType = N->getExtensionType();
2920   SDLoc dl(N);
2921
2922   if (getTypeAction(MaskVT) == TargetLowering::TypeWidenVector)
2923     Mask = GetWidenedVector(Mask);
2924   else {
2925     EVT BoolVT = getSetCCResultType(WidenVT);
2926
2927     // We can't use ModifyToType() because we should fill the mask with
2928     // zeroes
2929     unsigned WidenNumElts = BoolVT.getVectorNumElements();
2930     unsigned MaskNumElts = MaskVT.getVectorNumElements();
2931
2932     unsigned NumConcat = WidenNumElts / MaskNumElts;
2933     SmallVector<SDValue, 16> Ops(NumConcat);
2934     SDValue ZeroVal = DAG.getConstant(0, dl, MaskVT);
2935     Ops[0] = Mask;
2936     for (unsigned i = 1; i != NumConcat; ++i)
2937       Ops[i] = ZeroVal;
2938
2939     Mask = DAG.getNode(ISD::CONCAT_VECTORS, dl, BoolVT, Ops);
2940   }
2941
2942   SDValue Res = DAG.getMaskedLoad(WidenVT, dl, N->getChain(), N->getBasePtr(),
2943                                   Mask, Src0, N->getMemoryVT(),
2944                                   N->getMemOperand(), ExtType,
2945                                         N->isExpandingLoad());
2946   // Legalize the chain result - switch anything that used the old chain to
2947   // use the new one.
2948   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
2949   return Res;
2950 }
2951
2952 SDValue DAGTypeLegalizer::WidenVecRes_MGATHER(MaskedGatherSDNode *N) {
2953
2954   EVT WideVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2955   SDValue Mask = N->getMask();
2956   SDValue Src0 = GetWidenedVector(N->getValue());
2957   unsigned NumElts = WideVT.getVectorNumElements();
2958   SDLoc dl(N);
2959
2960   // The mask should be widened as well
2961   Mask = WidenTargetBoolean(Mask, WideVT, true);
2962
2963   // Widen the Index operand
2964   SDValue Index = N->getIndex();
2965   EVT WideIndexVT = EVT::getVectorVT(*DAG.getContext(),
2966                                      Index.getValueType().getScalarType(),
2967                                      NumElts);
2968   Index = ModifyToType(Index, WideIndexVT);
2969   SDValue Ops[] = { N->getChain(), Src0, Mask, N->getBasePtr(), Index };
2970   SDValue Res = DAG.getMaskedGather(DAG.getVTList(WideVT, MVT::Other),
2971                                     N->getMemoryVT(), dl, Ops,
2972                                     N->getMemOperand());
2973
2974   // Legalize the chain result - switch anything that used the old chain to
2975   // use the new one.
2976   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
2977   return Res;
2978 }
2979
2980 SDValue DAGTypeLegalizer::WidenVecRes_SCALAR_TO_VECTOR(SDNode *N) {
2981   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2982   return DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(N),
2983                      WidenVT, N->getOperand(0));
2984 }
2985
2986 // Return true if this is a node that could have two SETCCs as operands.
2987 static inline bool isLogicalMaskOp(unsigned Opcode) {
2988   switch (Opcode) {
2989   case ISD::AND:
2990   case ISD::OR:
2991   case ISD::XOR:
2992     return true;
2993   }
2994   return false;
2995 }
2996
2997 // This is used just for the assert in convertMask(). Check that this either
2998 // a SETCC or a previously handled SETCC by convertMask().
2999 #ifndef NDEBUG
3000 static inline bool isSETCCorConvertedSETCC(SDValue N) {
3001   if (N.getOpcode() == ISD::EXTRACT_SUBVECTOR)
3002     N = N.getOperand(0);
3003   else if (N.getOpcode() == ISD::CONCAT_VECTORS) {
3004     for (unsigned i = 1; i < N->getNumOperands(); ++i)
3005       if (!N->getOperand(i)->isUndef())
3006         return false;
3007     N = N.getOperand(0);
3008   }
3009
3010   if (N.getOpcode() == ISD::TRUNCATE)
3011     N = N.getOperand(0);
3012   else if (N.getOpcode() == ISD::SIGN_EXTEND)
3013     N = N.getOperand(0);
3014
3015   if (isLogicalMaskOp(N.getOpcode()))
3016     return isSETCCorConvertedSETCC(N.getOperand(0)) &&
3017            isSETCCorConvertedSETCC(N.getOperand(1));
3018
3019   return (N.getOpcode() == ISD::SETCC ||
3020           ISD::isBuildVectorOfConstantSDNodes(N.getNode()));
3021 }
3022 #endif
3023
3024 // Return a mask of vector type MaskVT to replace InMask. Also adjust MaskVT
3025 // to ToMaskVT if needed with vector extension or truncation.
3026 SDValue DAGTypeLegalizer::convertMask(SDValue InMask, EVT MaskVT,
3027                                       EVT ToMaskVT) {
3028   // Currently a SETCC or a AND/OR/XOR with two SETCCs are handled.
3029   // FIXME: This code seems to be too restrictive, we might consider
3030   // generalizing it or dropping it.
3031   assert(isSETCCorConvertedSETCC(InMask) && "Unexpected mask argument.");
3032
3033   // Make a new Mask node, with a legal result VT.
3034   SmallVector<SDValue, 4> Ops;
3035   for (unsigned i = 0; i < InMask->getNumOperands(); ++i)
3036     Ops.push_back(InMask->getOperand(i));
3037   SDValue Mask = DAG.getNode(InMask->getOpcode(), SDLoc(InMask), MaskVT, Ops);
3038
3039   // If MaskVT has smaller or bigger elements than ToMaskVT, a vector sign
3040   // extend or truncate is needed.
3041   LLVMContext &Ctx = *DAG.getContext();
3042   unsigned MaskScalarBits = MaskVT.getScalarSizeInBits();
3043   unsigned ToMaskScalBits = ToMaskVT.getScalarSizeInBits();
3044   if (MaskScalarBits < ToMaskScalBits) {
3045     EVT ExtVT = EVT::getVectorVT(Ctx, ToMaskVT.getVectorElementType(),
3046                                  MaskVT.getVectorNumElements());
3047     Mask = DAG.getNode(ISD::SIGN_EXTEND, SDLoc(Mask), ExtVT, Mask);
3048   } else if (MaskScalarBits > ToMaskScalBits) {
3049     EVT TruncVT = EVT::getVectorVT(Ctx, ToMaskVT.getVectorElementType(),
3050                                    MaskVT.getVectorNumElements());
3051     Mask = DAG.getNode(ISD::TRUNCATE, SDLoc(Mask), TruncVT, Mask);
3052   }
3053
3054   assert(Mask->getValueType(0).getScalarSizeInBits() ==
3055              ToMaskVT.getScalarSizeInBits() &&
3056          "Mask should have the right element size by now.");
3057
3058   // Adjust Mask to the right number of elements.
3059   unsigned CurrMaskNumEls = Mask->getValueType(0).getVectorNumElements();
3060   if (CurrMaskNumEls > ToMaskVT.getVectorNumElements()) {
3061     MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
3062     SDValue ZeroIdx = DAG.getConstant(0, SDLoc(Mask), IdxTy);
3063     Mask = DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(Mask), ToMaskVT, Mask,
3064                        ZeroIdx);
3065   } else if (CurrMaskNumEls < ToMaskVT.getVectorNumElements()) {
3066     unsigned NumSubVecs = (ToMaskVT.getVectorNumElements() / CurrMaskNumEls);
3067     EVT SubVT = Mask->getValueType(0);
3068     SmallVector<SDValue, 16> SubConcatOps(NumSubVecs);
3069     SubConcatOps[0] = Mask;
3070     for (unsigned i = 1; i < NumSubVecs; ++i)
3071       SubConcatOps[i] = DAG.getUNDEF(SubVT);
3072     Mask =
3073         DAG.getNode(ISD::CONCAT_VECTORS, SDLoc(Mask), ToMaskVT, SubConcatOps);
3074   }
3075
3076   assert((Mask->getValueType(0) == ToMaskVT) &&
3077          "A mask of ToMaskVT should have been produced by now.");
3078
3079   return Mask;
3080 }
3081
3082 // Get the target mask VT, and widen if needed.
3083 EVT DAGTypeLegalizer::getSETCCWidenedResultTy(SDValue SetCC) {
3084   assert(SetCC->getOpcode() == ISD::SETCC);
3085   LLVMContext &Ctx = *DAG.getContext();
3086   EVT MaskVT = getSetCCResultType(SetCC->getOperand(0).getValueType());
3087   if (getTypeAction(MaskVT) == TargetLowering::TypeWidenVector)
3088     MaskVT = TLI.getTypeToTransformTo(Ctx, MaskVT);
3089   return MaskVT;
3090 }
3091
3092 // This method tries to handle VSELECT and its mask by legalizing operands
3093 // (which may require widening) and if needed adjusting the mask vector type
3094 // to match that of the VSELECT. Without it, many cases end up with
3095 // scalarization of the SETCC, with many unnecessary instructions.
3096 SDValue DAGTypeLegalizer::WidenVSELECTAndMask(SDNode *N) {
3097   LLVMContext &Ctx = *DAG.getContext();
3098   SDValue Cond = N->getOperand(0);
3099
3100   if (N->getOpcode() != ISD::VSELECT)
3101     return SDValue();
3102
3103   if (Cond->getOpcode() != ISD::SETCC && !isLogicalMaskOp(Cond->getOpcode()))
3104     return SDValue();
3105
3106   // If this is a splitted VSELECT that was previously already handled, do
3107   // nothing.
3108   if (Cond->getValueType(0).getScalarSizeInBits() != 1)
3109     return SDValue();
3110
3111   EVT VSelVT = N->getValueType(0);
3112   // Only handle vector types which are a power of 2.
3113   if (!isPowerOf2_64(VSelVT.getSizeInBits()))
3114     return SDValue();
3115
3116   // Don't touch if this will be scalarized.
3117   EVT FinalVT = VSelVT;
3118   while (getTypeAction(FinalVT) == TargetLowering::TypeSplitVector)
3119     FinalVT = FinalVT.getHalfNumVectorElementsVT(Ctx);
3120
3121   if (FinalVT.getVectorNumElements() == 1)
3122     return SDValue();
3123
3124   // If there is support for an i1 vector mask, don't touch.
3125   if (Cond.getOpcode() == ISD::SETCC) {
3126     EVT SetCCOpVT = Cond->getOperand(0).getValueType();
3127     while (TLI.getTypeAction(Ctx, SetCCOpVT) != TargetLowering::TypeLegal)
3128       SetCCOpVT = TLI.getTypeToTransformTo(Ctx, SetCCOpVT);
3129     EVT SetCCResVT = getSetCCResultType(SetCCOpVT);
3130     if (SetCCResVT.getScalarSizeInBits() == 1)
3131       return SDValue();
3132   }
3133
3134   // Get the VT and operands for VSELECT, and widen if needed.
3135   SDValue VSelOp1 = N->getOperand(1);
3136   SDValue VSelOp2 = N->getOperand(2);
3137   if (getTypeAction(VSelVT) == TargetLowering::TypeWidenVector) {
3138     VSelVT = TLI.getTypeToTransformTo(Ctx, VSelVT);
3139     VSelOp1 = GetWidenedVector(VSelOp1);
3140     VSelOp2 = GetWidenedVector(VSelOp2);
3141   }
3142
3143   // The mask of the VSELECT should have integer elements.
3144   EVT ToMaskVT = VSelVT;
3145   if (!ToMaskVT.getScalarType().isInteger())
3146     ToMaskVT = ToMaskVT.changeVectorElementTypeToInteger();
3147
3148   SDValue Mask;
3149   if (Cond->getOpcode() == ISD::SETCC) {
3150     EVT MaskVT = getSETCCWidenedResultTy(Cond);
3151     Mask = convertMask(Cond, MaskVT, ToMaskVT);
3152   } else if (isLogicalMaskOp(Cond->getOpcode()) &&
3153              Cond->getOperand(0).getOpcode() == ISD::SETCC &&
3154              Cond->getOperand(1).getOpcode() == ISD::SETCC) {
3155     // Cond is (AND/OR/XOR (SETCC, SETCC))
3156     SDValue SETCC0 = Cond->getOperand(0);
3157     SDValue SETCC1 = Cond->getOperand(1);
3158     EVT VT0 = getSETCCWidenedResultTy(SETCC0);
3159     EVT VT1 = getSETCCWidenedResultTy(SETCC1);
3160     unsigned ScalarBits0 = VT0.getScalarSizeInBits();
3161     unsigned ScalarBits1 = VT1.getScalarSizeInBits();
3162     unsigned ScalarBits_ToMask = ToMaskVT.getScalarSizeInBits();
3163     EVT MaskVT;
3164     // If the two SETCCs have different VTs, either extend/truncate one of
3165     // them to the other "towards" ToMaskVT, or truncate one and extend the
3166     // other to ToMaskVT.
3167     if (ScalarBits0 != ScalarBits1) {
3168       EVT NarrowVT = ((ScalarBits0 < ScalarBits1) ? VT0 : VT1);
3169       EVT WideVT = ((NarrowVT == VT0) ? VT1 : VT0);
3170       if (ScalarBits_ToMask >= WideVT.getScalarSizeInBits())
3171         MaskVT = WideVT;
3172       else if (ScalarBits_ToMask <= NarrowVT.getScalarSizeInBits())
3173         MaskVT = NarrowVT;
3174       else
3175         MaskVT = ToMaskVT;
3176     } else
3177       // If the two SETCCs have the same VT, don't change it.
3178       MaskVT = VT0;
3179
3180     // Make new SETCCs and logical nodes.
3181     SETCC0 = convertMask(SETCC0, VT0, MaskVT);
3182     SETCC1 = convertMask(SETCC1, VT1, MaskVT);
3183     Cond = DAG.getNode(Cond->getOpcode(), SDLoc(Cond), MaskVT, SETCC0, SETCC1);
3184
3185     // Convert the logical op for VSELECT if needed.
3186     Mask = convertMask(Cond, MaskVT, ToMaskVT);
3187   } else
3188     return SDValue();
3189
3190   return DAG.getNode(ISD::VSELECT, SDLoc(N), VSelVT, Mask, VSelOp1, VSelOp2);
3191 }
3192
3193 SDValue DAGTypeLegalizer::WidenVecRes_SELECT(SDNode *N) {
3194   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3195   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3196
3197   SDValue Cond1 = N->getOperand(0);
3198   EVT CondVT = Cond1.getValueType();
3199   if (CondVT.isVector()) {
3200     if (SDValue Res = WidenVSELECTAndMask(N))
3201       return Res;
3202
3203     EVT CondEltVT = CondVT.getVectorElementType();
3204     EVT CondWidenVT =  EVT::getVectorVT(*DAG.getContext(),
3205                                         CondEltVT, WidenNumElts);
3206     if (getTypeAction(CondVT) == TargetLowering::TypeWidenVector)
3207       Cond1 = GetWidenedVector(Cond1);
3208
3209     // If we have to split the condition there is no point in widening the
3210     // select. This would result in an cycle of widening the select ->
3211     // widening the condition operand -> splitting the condition operand ->
3212     // splitting the select -> widening the select. Instead split this select
3213     // further and widen the resulting type.
3214     if (getTypeAction(CondVT) == TargetLowering::TypeSplitVector) {
3215       SDValue SplitSelect = SplitVecOp_VSELECT(N, 0);
3216       SDValue Res = ModifyToType(SplitSelect, WidenVT);
3217       return Res;
3218     }
3219
3220     if (Cond1.getValueType() != CondWidenVT)
3221       Cond1 = ModifyToType(Cond1, CondWidenVT);
3222   }
3223
3224   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
3225   SDValue InOp2 = GetWidenedVector(N->getOperand(2));
3226   assert(InOp1.getValueType() == WidenVT && InOp2.getValueType() == WidenVT);
3227   return DAG.getNode(N->getOpcode(), SDLoc(N),
3228                      WidenVT, Cond1, InOp1, InOp2);
3229 }
3230
3231 SDValue DAGTypeLegalizer::WidenVecRes_SELECT_CC(SDNode *N) {
3232   SDValue InOp1 = GetWidenedVector(N->getOperand(2));
3233   SDValue InOp2 = GetWidenedVector(N->getOperand(3));
3234   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
3235                      InOp1.getValueType(), N->getOperand(0),
3236                      N->getOperand(1), InOp1, InOp2, N->getOperand(4));
3237 }
3238
3239 SDValue DAGTypeLegalizer::WidenVecRes_SETCC(SDNode *N) {
3240   assert(N->getValueType(0).isVector() ==
3241          N->getOperand(0).getValueType().isVector() &&
3242          "Scalar/Vector type mismatch");
3243   if (N->getValueType(0).isVector()) return WidenVecRes_VSETCC(N);
3244
3245   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3246   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
3247   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3248   return DAG.getNode(ISD::SETCC, SDLoc(N), WidenVT,
3249                      InOp1, InOp2, N->getOperand(2));
3250 }
3251
3252 SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) {
3253  EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3254  return DAG.getUNDEF(WidenVT);
3255 }
3256
3257 SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N) {
3258   EVT VT = N->getValueType(0);
3259   SDLoc dl(N);
3260
3261   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3262   unsigned NumElts = VT.getVectorNumElements();
3263   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3264
3265   SDValue InOp1 = GetWidenedVector(N->getOperand(0));
3266   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3267
3268   // Adjust mask based on new input vector length.
3269   SmallVector<int, 16> NewMask;
3270   for (unsigned i = 0; i != NumElts; ++i) {
3271     int Idx = N->getMaskElt(i);
3272     if (Idx < (int)NumElts)
3273       NewMask.push_back(Idx);
3274     else
3275       NewMask.push_back(Idx - NumElts + WidenNumElts);
3276   }
3277   for (unsigned i = NumElts; i != WidenNumElts; ++i)
3278     NewMask.push_back(-1);
3279   return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, NewMask);
3280 }
3281
3282 SDValue DAGTypeLegalizer::WidenVecRes_VSETCC(SDNode *N) {
3283   assert(N->getValueType(0).isVector() &&
3284          N->getOperand(0).getValueType().isVector() &&
3285          "Operands must be vectors");
3286   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
3287   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3288
3289   SDValue InOp1 = N->getOperand(0);
3290   EVT InVT = InOp1.getValueType();
3291   assert(InVT.isVector() && "can not widen non-vector type");
3292   EVT WidenInVT = EVT::getVectorVT(*DAG.getContext(),
3293                                    InVT.getVectorElementType(), WidenNumElts);
3294
3295   // The input and output types often differ here, and it could be that while
3296   // we'd prefer to widen the result type, the input operands have been split.
3297   // In this case, we also need to split the result of this node as well.
3298   if (getTypeAction(InVT) == TargetLowering::TypeSplitVector) {
3299     SDValue SplitVSetCC = SplitVecOp_VSETCC(N);
3300     SDValue Res = ModifyToType(SplitVSetCC, WidenVT);
3301     return Res;
3302   }
3303
3304   InOp1 = GetWidenedVector(InOp1);
3305   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
3306
3307   // Assume that the input and output will be widen appropriately.  If not,
3308   // we will have to unroll it at some point.
3309   assert(InOp1.getValueType() == WidenInVT &&
3310          InOp2.getValueType() == WidenInVT &&
3311          "Input not widened to expected type!");
3312   (void)WidenInVT;
3313   return DAG.getNode(ISD::SETCC, SDLoc(N),
3314                      WidenVT, InOp1, InOp2, N->getOperand(2));
3315 }
3316
3317
3318 //===----------------------------------------------------------------------===//
3319 // Widen Vector Operand
3320 //===----------------------------------------------------------------------===//
3321 bool DAGTypeLegalizer::WidenVectorOperand(SDNode *N, unsigned OpNo) {
3322   DEBUG(dbgs() << "Widen node operand " << OpNo << ": ";
3323         N->dump(&DAG);
3324         dbgs() << "\n");
3325   SDValue Res = SDValue();
3326
3327   // See if the target wants to custom widen this node.
3328   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
3329     return false;
3330
3331   switch (N->getOpcode()) {
3332   default:
3333 #ifndef NDEBUG
3334     dbgs() << "WidenVectorOperand op #" << OpNo << ": ";
3335     N->dump(&DAG);
3336     dbgs() << "\n";
3337 #endif
3338     llvm_unreachable("Do not know how to widen this operator's operand!");
3339
3340   case ISD::BITCAST:            Res = WidenVecOp_BITCAST(N); break;
3341   case ISD::CONCAT_VECTORS:     Res = WidenVecOp_CONCAT_VECTORS(N); break;
3342   case ISD::EXTRACT_SUBVECTOR:  Res = WidenVecOp_EXTRACT_SUBVECTOR(N); break;
3343   case ISD::EXTRACT_VECTOR_ELT: Res = WidenVecOp_EXTRACT_VECTOR_ELT(N); break;
3344   case ISD::STORE:              Res = WidenVecOp_STORE(N); break;
3345   case ISD::MSTORE:             Res = WidenVecOp_MSTORE(N, OpNo); break;
3346   case ISD::MSCATTER:           Res = WidenVecOp_MSCATTER(N, OpNo); break;
3347   case ISD::SETCC:              Res = WidenVecOp_SETCC(N); break;
3348   case ISD::FCOPYSIGN:          Res = WidenVecOp_FCOPYSIGN(N); break;
3349
3350   case ISD::ANY_EXTEND:
3351   case ISD::SIGN_EXTEND:
3352   case ISD::ZERO_EXTEND:
3353     Res = WidenVecOp_EXTEND(N);
3354     break;
3355
3356   case ISD::FP_EXTEND:
3357   case ISD::FP_TO_SINT:
3358   case ISD::FP_TO_UINT:
3359   case ISD::SINT_TO_FP:
3360   case ISD::UINT_TO_FP:
3361   case ISD::TRUNCATE:
3362     Res = WidenVecOp_Convert(N);
3363     break;
3364   }
3365
3366   // If Res is null, the sub-method took care of registering the result.
3367   if (!Res.getNode()) return false;
3368
3369   // If the result is N, the sub-method updated N in place.  Tell the legalizer
3370   // core about this.
3371   if (Res.getNode() == N)
3372     return true;
3373
3374
3375   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
3376          "Invalid operand expansion");
3377
3378   ReplaceValueWith(SDValue(N, 0), Res);
3379   return false;
3380 }
3381
3382 SDValue DAGTypeLegalizer::WidenVecOp_EXTEND(SDNode *N) {
3383   SDLoc DL(N);
3384   EVT VT = N->getValueType(0);
3385
3386   SDValue InOp = N->getOperand(0);
3387   // If some legalization strategy other than widening is used on the operand,
3388   // we can't safely assume that just extending the low lanes is the correct
3389   // transformation.
3390   if (getTypeAction(InOp.getValueType()) != TargetLowering::TypeWidenVector)
3391     return WidenVecOp_Convert(N);
3392   InOp = GetWidenedVector(InOp);
3393   assert(VT.getVectorNumElements() <
3394              InOp.getValueType().getVectorNumElements() &&
3395          "Input wasn't widened!");
3396
3397   // We may need to further widen the operand until it has the same total
3398   // vector size as the result.
3399   EVT InVT = InOp.getValueType();
3400   if (InVT.getSizeInBits() != VT.getSizeInBits()) {
3401     EVT InEltVT = InVT.getVectorElementType();
3402     for (int i = MVT::FIRST_VECTOR_VALUETYPE, e = MVT::LAST_VECTOR_VALUETYPE; i < e; ++i) {
3403       EVT FixedVT = (MVT::SimpleValueType)i;
3404       EVT FixedEltVT = FixedVT.getVectorElementType();
3405       if (TLI.isTypeLegal(FixedVT) &&
3406           FixedVT.getSizeInBits() == VT.getSizeInBits() &&
3407           FixedEltVT == InEltVT) {
3408         assert(FixedVT.getVectorNumElements() >= VT.getVectorNumElements() &&
3409                "Not enough elements in the fixed type for the operand!");
3410         assert(FixedVT.getVectorNumElements() != InVT.getVectorNumElements() &&
3411                "We can't have the same type as we started with!");
3412         if (FixedVT.getVectorNumElements() > InVT.getVectorNumElements())
3413           InOp = DAG.getNode(
3414               ISD::INSERT_SUBVECTOR, DL, FixedVT, DAG.getUNDEF(FixedVT), InOp,
3415               DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
3416         else
3417           InOp = DAG.getNode(
3418               ISD::EXTRACT_SUBVECTOR, DL, FixedVT, InOp,
3419               DAG.getConstant(0, DL, TLI.getVectorIdxTy(DAG.getDataLayout())));
3420         break;
3421       }
3422     }
3423     InVT = InOp.getValueType();
3424     if (InVT.getSizeInBits() != VT.getSizeInBits())
3425       // We couldn't find a legal vector type that was a widening of the input
3426       // and could be extended in-register to the result type, so we have to
3427       // scalarize.
3428       return WidenVecOp_Convert(N);
3429   }
3430
3431   // Use special DAG nodes to represent the operation of extending the
3432   // low lanes.
3433   switch (N->getOpcode()) {
3434   default:
3435     llvm_unreachable("Extend legalization on on extend operation!");
3436   case ISD::ANY_EXTEND:
3437     return DAG.getAnyExtendVectorInReg(InOp, DL, VT);
3438   case ISD::SIGN_EXTEND:
3439     return DAG.getSignExtendVectorInReg(InOp, DL, VT);
3440   case ISD::ZERO_EXTEND:
3441     return DAG.getZeroExtendVectorInReg(InOp, DL, VT);
3442   }
3443 }
3444
3445 SDValue DAGTypeLegalizer::WidenVecOp_FCOPYSIGN(SDNode *N) {
3446   // The result (and first input) is legal, but the second input is illegal.
3447   // We can't do much to fix that, so just unroll and let the extracts off of
3448   // the second input be widened as needed later.
3449   return DAG.UnrollVectorOp(N);
3450 }
3451
3452 SDValue DAGTypeLegalizer::WidenVecOp_Convert(SDNode *N) {
3453   // Since the result is legal and the input is illegal, it is unlikely that we
3454   // can fix the input to a legal type so unroll the convert into some scalar
3455   // code and create a nasty build vector.
3456   EVT VT = N->getValueType(0);
3457   EVT EltVT = VT.getVectorElementType();
3458   SDLoc dl(N);
3459   unsigned NumElts = VT.getVectorNumElements();
3460   SDValue InOp = N->getOperand(0);
3461   if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
3462     InOp = GetWidenedVector(InOp);
3463   EVT InVT = InOp.getValueType();
3464   EVT InEltVT = InVT.getVectorElementType();
3465
3466   unsigned Opcode = N->getOpcode();
3467   SmallVector<SDValue, 16> Ops(NumElts);
3468   for (unsigned i=0; i < NumElts; ++i)
3469     Ops[i] = DAG.getNode(
3470         Opcode, dl, EltVT,
3471         DAG.getNode(
3472             ISD::EXTRACT_VECTOR_ELT, dl, InEltVT, InOp,
3473             DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout()))));
3474
3475   return DAG.getBuildVector(VT, dl, Ops);
3476 }
3477
3478 SDValue DAGTypeLegalizer::WidenVecOp_BITCAST(SDNode *N) {
3479   EVT VT = N->getValueType(0);
3480   SDValue InOp = GetWidenedVector(N->getOperand(0));
3481   EVT InWidenVT = InOp.getValueType();
3482   SDLoc dl(N);
3483
3484   // Check if we can convert between two legal vector types and extract.
3485   unsigned InWidenSize = InWidenVT.getSizeInBits();
3486   unsigned Size = VT.getSizeInBits();
3487   // x86mmx is not an acceptable vector element type, so don't try.
3488   if (InWidenSize % Size == 0 && !VT.isVector() && VT != MVT::x86mmx) {
3489     unsigned NewNumElts = InWidenSize / Size;
3490     EVT NewVT = EVT::getVectorVT(*DAG.getContext(), VT, NewNumElts);
3491     if (TLI.isTypeLegal(NewVT)) {
3492       SDValue BitOp = DAG.getNode(ISD::BITCAST, dl, NewVT, InOp);
3493       return DAG.getNode(
3494           ISD::EXTRACT_VECTOR_ELT, dl, VT, BitOp,
3495           DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3496     }
3497   }
3498
3499   return CreateStackStoreLoad(InOp, VT);
3500 }
3501
3502 SDValue DAGTypeLegalizer::WidenVecOp_CONCAT_VECTORS(SDNode *N) {
3503   // If the input vector is not legal, it is likely that we will not find a
3504   // legal vector of the same size. Replace the concatenate vector with a
3505   // nasty build vector.
3506   EVT VT = N->getValueType(0);
3507   EVT EltVT = VT.getVectorElementType();
3508   SDLoc dl(N);
3509   unsigned NumElts = VT.getVectorNumElements();
3510   SmallVector<SDValue, 16> Ops(NumElts);
3511
3512   EVT InVT = N->getOperand(0).getValueType();
3513   unsigned NumInElts = InVT.getVectorNumElements();
3514
3515   unsigned Idx = 0;
3516   unsigned NumOperands = N->getNumOperands();
3517   for (unsigned i=0; i < NumOperands; ++i) {
3518     SDValue InOp = N->getOperand(i);
3519     if (getTypeAction(InOp.getValueType()) == TargetLowering::TypeWidenVector)
3520       InOp = GetWidenedVector(InOp);
3521     for (unsigned j=0; j < NumInElts; ++j)
3522       Ops[Idx++] = DAG.getNode(
3523           ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
3524           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3525   }
3526   return DAG.getBuildVector(VT, dl, Ops);
3527 }
3528
3529 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
3530   SDValue InOp = GetWidenedVector(N->getOperand(0));
3531   return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(N),
3532                      N->getValueType(0), InOp, N->getOperand(1));
3533 }
3534
3535 SDValue DAGTypeLegalizer::WidenVecOp_EXTRACT_VECTOR_ELT(SDNode *N) {
3536   SDValue InOp = GetWidenedVector(N->getOperand(0));
3537   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(N),
3538                      N->getValueType(0), InOp, N->getOperand(1));
3539 }
3540
3541 SDValue DAGTypeLegalizer::WidenVecOp_STORE(SDNode *N) {
3542   // We have to widen the value, but we want only to store the original
3543   // vector type.
3544   StoreSDNode *ST = cast<StoreSDNode>(N);
3545
3546   SmallVector<SDValue, 16> StChain;
3547   if (ST->isTruncatingStore())
3548     GenWidenVectorTruncStores(StChain, ST);
3549   else
3550     GenWidenVectorStores(StChain, ST);
3551
3552   if (StChain.size() == 1)
3553     return StChain[0];
3554   else
3555     return DAG.getNode(ISD::TokenFactor, SDLoc(ST), MVT::Other, StChain);
3556 }
3557
3558 SDValue DAGTypeLegalizer::WidenVecOp_MSTORE(SDNode *N, unsigned OpNo) {
3559   MaskedStoreSDNode *MST = cast<MaskedStoreSDNode>(N);
3560   SDValue Mask = MST->getMask();
3561   EVT MaskVT = Mask.getValueType();
3562   SDValue StVal = MST->getValue();
3563   // Widen the value
3564   SDValue WideVal = GetWidenedVector(StVal);
3565   SDLoc dl(N);
3566
3567   if (OpNo == 2 || getTypeAction(MaskVT) == TargetLowering::TypeWidenVector)
3568     Mask = GetWidenedVector(Mask);
3569   else {
3570     // The mask should be widened as well.
3571     EVT BoolVT = getSetCCResultType(WideVal.getValueType());
3572     // We can't use ModifyToType() because we should fill the mask with
3573     // zeroes.
3574     unsigned WidenNumElts = BoolVT.getVectorNumElements();
3575     unsigned MaskNumElts = MaskVT.getVectorNumElements();
3576
3577     unsigned NumConcat = WidenNumElts / MaskNumElts;
3578     SmallVector<SDValue, 16> Ops(NumConcat);
3579     SDValue ZeroVal = DAG.getConstant(0, dl, MaskVT);
3580     Ops[0] = Mask;
3581     for (unsigned i = 1; i != NumConcat; ++i)
3582       Ops[i] = ZeroVal;
3583
3584     Mask = DAG.getNode(ISD::CONCAT_VECTORS, dl, BoolVT, Ops);
3585   }
3586   assert(Mask.getValueType().getVectorNumElements() ==
3587          WideVal.getValueType().getVectorNumElements() &&
3588          "Mask and data vectors should have the same number of elements");
3589   return DAG.getMaskedStore(MST->getChain(), dl, WideVal, MST->getBasePtr(),
3590                             Mask, MST->getMemoryVT(), MST->getMemOperand(),
3591                             false, MST->isCompressingStore());
3592 }
3593
3594 SDValue DAGTypeLegalizer::WidenVecOp_MSCATTER(SDNode *N, unsigned OpNo) {
3595   assert(OpNo == 1 && "Can widen only data operand of mscatter");
3596   MaskedScatterSDNode *MSC = cast<MaskedScatterSDNode>(N);
3597   SDValue DataOp = MSC->getValue();
3598   SDValue Mask = MSC->getMask();
3599
3600   // Widen the value.
3601   SDValue WideVal = GetWidenedVector(DataOp);
3602   EVT WideVT = WideVal.getValueType();
3603   unsigned NumElts = WideVal.getValueType().getVectorNumElements();
3604   SDLoc dl(N);
3605
3606   // The mask should be widened as well.
3607   Mask = WidenTargetBoolean(Mask, WideVT, true);
3608
3609   // Widen index.
3610   SDValue Index = MSC->getIndex();
3611   EVT WideIndexVT = EVT::getVectorVT(*DAG.getContext(),
3612                                      Index.getValueType().getScalarType(),
3613                                      NumElts);
3614   Index = ModifyToType(Index, WideIndexVT);
3615
3616   SDValue Ops[] = {MSC->getChain(), WideVal, Mask, MSC->getBasePtr(), Index};
3617   return DAG.getMaskedScatter(DAG.getVTList(MVT::Other),
3618                               MSC->getMemoryVT(), dl, Ops,
3619                               MSC->getMemOperand());
3620 }
3621
3622 SDValue DAGTypeLegalizer::WidenVecOp_SETCC(SDNode *N) {
3623   SDValue InOp0 = GetWidenedVector(N->getOperand(0));
3624   SDValue InOp1 = GetWidenedVector(N->getOperand(1));
3625   SDLoc dl(N);
3626
3627   // WARNING: In this code we widen the compare instruction with garbage.
3628   // This garbage may contain denormal floats which may be slow. Is this a real
3629   // concern ? Should we zero the unused lanes if this is a float compare ?
3630
3631   // Get a new SETCC node to compare the newly widened operands.
3632   // Only some of the compared elements are legal.
3633   EVT SVT = TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(),
3634                                    InOp0.getValueType());
3635   SDValue WideSETCC = DAG.getNode(ISD::SETCC, SDLoc(N),
3636                      SVT, InOp0, InOp1, N->getOperand(2));
3637
3638   // Extract the needed results from the result vector.
3639   EVT ResVT = EVT::getVectorVT(*DAG.getContext(),
3640                                SVT.getVectorElementType(),
3641                                N->getValueType(0).getVectorNumElements());
3642   SDValue CC = DAG.getNode(
3643       ISD::EXTRACT_SUBVECTOR, dl, ResVT, WideSETCC,
3644       DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3645
3646   return PromoteTargetBoolean(CC, N->getValueType(0));
3647 }
3648
3649
3650 //===----------------------------------------------------------------------===//
3651 // Vector Widening Utilities
3652 //===----------------------------------------------------------------------===//
3653
3654 // Utility function to find the type to chop up a widen vector for load/store
3655 //  TLI:       Target lowering used to determine legal types.
3656 //  Width:     Width left need to load/store.
3657 //  WidenVT:   The widen vector type to load to/store from
3658 //  Align:     If 0, don't allow use of a wider type
3659 //  WidenEx:   If Align is not 0, the amount additional we can load/store from.
3660
3661 static EVT FindMemType(SelectionDAG& DAG, const TargetLowering &TLI,
3662                        unsigned Width, EVT WidenVT,
3663                        unsigned Align = 0, unsigned WidenEx = 0) {
3664   EVT WidenEltVT = WidenVT.getVectorElementType();
3665   unsigned WidenWidth = WidenVT.getSizeInBits();
3666   unsigned WidenEltWidth = WidenEltVT.getSizeInBits();
3667   unsigned AlignInBits = Align*8;
3668
3669   // If we have one element to load/store, return it.
3670   EVT RetVT = WidenEltVT;
3671   if (Width == WidenEltWidth)
3672     return RetVT;
3673
3674   // See if there is larger legal integer than the element type to load/store.
3675   unsigned VT;
3676   for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE;
3677        VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) {
3678     EVT MemVT((MVT::SimpleValueType) VT);
3679     unsigned MemVTWidth = MemVT.getSizeInBits();
3680     if (MemVT.getSizeInBits() <= WidenEltWidth)
3681       break;
3682     auto Action = TLI.getTypeAction(*DAG.getContext(), MemVT);
3683     if ((Action == TargetLowering::TypeLegal ||
3684          Action == TargetLowering::TypePromoteInteger) &&
3685         (WidenWidth % MemVTWidth) == 0 &&
3686         isPowerOf2_32(WidenWidth / MemVTWidth) &&
3687         (MemVTWidth <= Width ||
3688          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
3689       RetVT = MemVT;
3690       break;
3691     }
3692   }
3693
3694   // See if there is a larger vector type to load/store that has the same vector
3695   // element type and is evenly divisible with the WidenVT.
3696   for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE;
3697        VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) {
3698     EVT MemVT = (MVT::SimpleValueType) VT;
3699     unsigned MemVTWidth = MemVT.getSizeInBits();
3700     if (TLI.isTypeLegal(MemVT) && WidenEltVT == MemVT.getVectorElementType() &&
3701         (WidenWidth % MemVTWidth) == 0 &&
3702         isPowerOf2_32(WidenWidth / MemVTWidth) &&
3703         (MemVTWidth <= Width ||
3704          (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
3705       if (RetVT.getSizeInBits() < MemVTWidth || MemVT == WidenVT)
3706         return MemVT;
3707     }
3708   }
3709
3710   return RetVT;
3711 }
3712
3713 // Builds a vector type from scalar loads
3714 //  VecTy: Resulting Vector type
3715 //  LDOps: Load operators to build a vector type
3716 //  [Start,End) the list of loads to use.
3717 static SDValue BuildVectorFromScalar(SelectionDAG& DAG, EVT VecTy,
3718                                      SmallVectorImpl<SDValue> &LdOps,
3719                                      unsigned Start, unsigned End) {
3720   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3721   SDLoc dl(LdOps[Start]);
3722   EVT LdTy = LdOps[Start].getValueType();
3723   unsigned Width = VecTy.getSizeInBits();
3724   unsigned NumElts = Width / LdTy.getSizeInBits();
3725   EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), LdTy, NumElts);
3726
3727   unsigned Idx = 1;
3728   SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT,LdOps[Start]);
3729
3730   for (unsigned i = Start + 1; i != End; ++i) {
3731     EVT NewLdTy = LdOps[i].getValueType();
3732     if (NewLdTy != LdTy) {
3733       NumElts = Width / NewLdTy.getSizeInBits();
3734       NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewLdTy, NumElts);
3735       VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, VecOp);
3736       // Readjust position and vector position based on new load type.
3737       Idx = Idx * LdTy.getSizeInBits() / NewLdTy.getSizeInBits();
3738       LdTy = NewLdTy;
3739     }
3740     VecOp = DAG.getNode(
3741         ISD::INSERT_VECTOR_ELT, dl, NewVecVT, VecOp, LdOps[i],
3742         DAG.getConstant(Idx++, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3743   }
3744   return DAG.getNode(ISD::BITCAST, dl, VecTy, VecOp);
3745 }
3746
3747 SDValue DAGTypeLegalizer::GenWidenVectorLoads(SmallVectorImpl<SDValue> &LdChain,
3748                                               LoadSDNode *LD) {
3749   // The strategy assumes that we can efficiently load power-of-two widths.
3750   // The routine chops the vector into the largest vector loads with the same
3751   // element type or scalar loads and then recombines it to the widen vector
3752   // type.
3753   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
3754   unsigned WidenWidth = WidenVT.getSizeInBits();
3755   EVT LdVT    = LD->getMemoryVT();
3756   SDLoc dl(LD);
3757   assert(LdVT.isVector() && WidenVT.isVector());
3758   assert(LdVT.getVectorElementType() == WidenVT.getVectorElementType());
3759
3760   // Load information
3761   SDValue Chain = LD->getChain();
3762   SDValue BasePtr = LD->getBasePtr();
3763   unsigned Align = LD->getAlignment();
3764   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
3765   AAMDNodes AAInfo = LD->getAAInfo();
3766
3767   int LdWidth = LdVT.getSizeInBits();
3768   int WidthDiff = WidenWidth - LdWidth;
3769   unsigned LdAlign = LD->isVolatile() ? 0 : Align; // Allow wider loads.
3770
3771   // Find the vector type that can load from.
3772   EVT NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
3773   int NewVTWidth = NewVT.getSizeInBits();
3774   SDValue LdOp = DAG.getLoad(NewVT, dl, Chain, BasePtr, LD->getPointerInfo(),
3775                              Align, MMOFlags, AAInfo);
3776   LdChain.push_back(LdOp.getValue(1));
3777
3778   // Check if we can load the element with one instruction.
3779   if (LdWidth <= NewVTWidth) {
3780     if (!NewVT.isVector()) {
3781       unsigned NumElts = WidenWidth / NewVTWidth;
3782       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
3783       SDValue VecOp = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NewVecVT, LdOp);
3784       return DAG.getNode(ISD::BITCAST, dl, WidenVT, VecOp);
3785     }
3786     if (NewVT == WidenVT)
3787       return LdOp;
3788
3789     assert(WidenWidth % NewVTWidth == 0);
3790     unsigned NumConcat = WidenWidth / NewVTWidth;
3791     SmallVector<SDValue, 16> ConcatOps(NumConcat);
3792     SDValue UndefVal = DAG.getUNDEF(NewVT);
3793     ConcatOps[0] = LdOp;
3794     for (unsigned i = 1; i != NumConcat; ++i)
3795       ConcatOps[i] = UndefVal;
3796     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, ConcatOps);
3797   }
3798
3799   // Load vector by using multiple loads from largest vector to scalar.
3800   SmallVector<SDValue, 16> LdOps;
3801   LdOps.push_back(LdOp);
3802
3803   LdWidth -= NewVTWidth;
3804   unsigned Offset = 0;
3805
3806   while (LdWidth > 0) {
3807     unsigned Increment = NewVTWidth / 8;
3808     Offset += Increment;
3809     BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
3810                           DAG.getConstant(Increment, dl, BasePtr.getValueType()));
3811
3812     SDValue L;
3813     if (LdWidth < NewVTWidth) {
3814       // The current type we are using is too large. Find a better size.
3815       NewVT = FindMemType(DAG, TLI, LdWidth, WidenVT, LdAlign, WidthDiff);
3816       NewVTWidth = NewVT.getSizeInBits();
3817       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
3818                       LD->getPointerInfo().getWithOffset(Offset),
3819                       MinAlign(Align, Increment), MMOFlags, AAInfo);
3820       LdChain.push_back(L.getValue(1));
3821       if (L->getValueType(0).isVector() && NewVTWidth >= LdWidth) {
3822         // Later code assumes the vector loads produced will be mergeable, so we
3823         // must pad the final entry up to the previous width. Scalars are
3824         // combined separately.
3825         SmallVector<SDValue, 16> Loads;
3826         Loads.push_back(L);
3827         unsigned size = L->getValueSizeInBits(0);
3828         while (size < LdOp->getValueSizeInBits(0)) {
3829           Loads.push_back(DAG.getUNDEF(L->getValueType(0)));
3830           size += L->getValueSizeInBits(0);
3831         }
3832         L = DAG.getNode(ISD::CONCAT_VECTORS, dl, LdOp->getValueType(0), Loads);
3833       }
3834     } else {
3835       L = DAG.getLoad(NewVT, dl, Chain, BasePtr,
3836                       LD->getPointerInfo().getWithOffset(Offset),
3837                       MinAlign(Align, Increment), MMOFlags, AAInfo);
3838       LdChain.push_back(L.getValue(1));
3839     }
3840
3841     LdOps.push_back(L);
3842
3843
3844     LdWidth -= NewVTWidth;
3845   }
3846
3847   // Build the vector from the load operations.
3848   unsigned End = LdOps.size();
3849   if (!LdOps[0].getValueType().isVector())
3850     // All the loads are scalar loads.
3851     return BuildVectorFromScalar(DAG, WidenVT, LdOps, 0, End);
3852
3853   // If the load contains vectors, build the vector using concat vector.
3854   // All of the vectors used to load are power-of-2, and the scalar loads can be
3855   // combined to make a power-of-2 vector.
3856   SmallVector<SDValue, 16> ConcatOps(End);
3857   int i = End - 1;
3858   int Idx = End;
3859   EVT LdTy = LdOps[i].getValueType();
3860   // First, combine the scalar loads to a vector.
3861   if (!LdTy.isVector())  {
3862     for (--i; i >= 0; --i) {
3863       LdTy = LdOps[i].getValueType();
3864       if (LdTy.isVector())
3865         break;
3866     }
3867     ConcatOps[--Idx] = BuildVectorFromScalar(DAG, LdTy, LdOps, i + 1, End);
3868   }
3869   ConcatOps[--Idx] = LdOps[i];
3870   for (--i; i >= 0; --i) {
3871     EVT NewLdTy = LdOps[i].getValueType();
3872     if (NewLdTy != LdTy) {
3873       // Create a larger vector.
3874       ConcatOps[End-1] = DAG.getNode(ISD::CONCAT_VECTORS, dl, NewLdTy,
3875                                      makeArrayRef(&ConcatOps[Idx], End - Idx));
3876       Idx = End - 1;
3877       LdTy = NewLdTy;
3878     }
3879     ConcatOps[--Idx] = LdOps[i];
3880   }
3881
3882   if (WidenWidth == LdTy.getSizeInBits() * (End - Idx))
3883     return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT,
3884                        makeArrayRef(&ConcatOps[Idx], End - Idx));
3885
3886   // We need to fill the rest with undefs to build the vector.
3887   unsigned NumOps = WidenWidth / LdTy.getSizeInBits();
3888   SmallVector<SDValue, 16> WidenOps(NumOps);
3889   SDValue UndefVal = DAG.getUNDEF(LdTy);
3890   {
3891     unsigned i = 0;
3892     for (; i != End-Idx; ++i)
3893       WidenOps[i] = ConcatOps[Idx+i];
3894     for (; i != NumOps; ++i)
3895       WidenOps[i] = UndefVal;
3896   }
3897   return DAG.getNode(ISD::CONCAT_VECTORS, dl, WidenVT, WidenOps);
3898 }
3899
3900 SDValue
3901 DAGTypeLegalizer::GenWidenVectorExtLoads(SmallVectorImpl<SDValue> &LdChain,
3902                                          LoadSDNode *LD,
3903                                          ISD::LoadExtType ExtType) {
3904   // For extension loads, it may not be more efficient to chop up the vector
3905   // and then extend it. Instead, we unroll the load and build a new vector.
3906   EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(),LD->getValueType(0));
3907   EVT LdVT    = LD->getMemoryVT();
3908   SDLoc dl(LD);
3909   assert(LdVT.isVector() && WidenVT.isVector());
3910
3911   // Load information
3912   SDValue Chain = LD->getChain();
3913   SDValue BasePtr = LD->getBasePtr();
3914   unsigned Align = LD->getAlignment();
3915   MachineMemOperand::Flags MMOFlags = LD->getMemOperand()->getFlags();
3916   AAMDNodes AAInfo = LD->getAAInfo();
3917
3918   EVT EltVT = WidenVT.getVectorElementType();
3919   EVT LdEltVT = LdVT.getVectorElementType();
3920   unsigned NumElts = LdVT.getVectorNumElements();
3921
3922   // Load each element and widen.
3923   unsigned WidenNumElts = WidenVT.getVectorNumElements();
3924   SmallVector<SDValue, 16> Ops(WidenNumElts);
3925   unsigned Increment = LdEltVT.getSizeInBits() / 8;
3926   Ops[0] =
3927       DAG.getExtLoad(ExtType, dl, EltVT, Chain, BasePtr, LD->getPointerInfo(),
3928                      LdEltVT, Align, MMOFlags, AAInfo);
3929   LdChain.push_back(Ops[0].getValue(1));
3930   unsigned i = 0, Offset = Increment;
3931   for (i=1; i < NumElts; ++i, Offset += Increment) {
3932     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
3933                                      BasePtr,
3934                                      DAG.getConstant(Offset, dl,
3935                                                      BasePtr.getValueType()));
3936     Ops[i] = DAG.getExtLoad(ExtType, dl, EltVT, Chain, NewBasePtr,
3937                             LD->getPointerInfo().getWithOffset(Offset), LdEltVT,
3938                             Align, MMOFlags, AAInfo);
3939     LdChain.push_back(Ops[i].getValue(1));
3940   }
3941
3942   // Fill the rest with undefs.
3943   SDValue UndefVal = DAG.getUNDEF(EltVT);
3944   for (; i != WidenNumElts; ++i)
3945     Ops[i] = UndefVal;
3946
3947   return DAG.getBuildVector(WidenVT, dl, Ops);
3948 }
3949
3950 void DAGTypeLegalizer::GenWidenVectorStores(SmallVectorImpl<SDValue> &StChain,
3951                                             StoreSDNode *ST) {
3952   // The strategy assumes that we can efficiently store power-of-two widths.
3953   // The routine chops the vector into the largest vector stores with the same
3954   // element type or scalar stores.
3955   SDValue  Chain = ST->getChain();
3956   SDValue  BasePtr = ST->getBasePtr();
3957   unsigned Align = ST->getAlignment();
3958   MachineMemOperand::Flags MMOFlags = ST->getMemOperand()->getFlags();
3959   AAMDNodes AAInfo = ST->getAAInfo();
3960   SDValue  ValOp = GetWidenedVector(ST->getValue());
3961   SDLoc dl(ST);
3962
3963   EVT StVT = ST->getMemoryVT();
3964   unsigned StWidth = StVT.getSizeInBits();
3965   EVT ValVT = ValOp.getValueType();
3966   unsigned ValWidth = ValVT.getSizeInBits();
3967   EVT ValEltVT = ValVT.getVectorElementType();
3968   unsigned ValEltWidth = ValEltVT.getSizeInBits();
3969   assert(StVT.getVectorElementType() == ValEltVT);
3970
3971   int Idx = 0;          // current index to store
3972   unsigned Offset = 0;  // offset from base to store
3973   while (StWidth != 0) {
3974     // Find the largest vector type we can store with.
3975     EVT NewVT = FindMemType(DAG, TLI, StWidth, ValVT);
3976     unsigned NewVTWidth = NewVT.getSizeInBits();
3977     unsigned Increment = NewVTWidth / 8;
3978     if (NewVT.isVector()) {
3979       unsigned NumVTElts = NewVT.getVectorNumElements();
3980       do {
3981         SDValue EOp = DAG.getNode(
3982             ISD::EXTRACT_SUBVECTOR, dl, NewVT, ValOp,
3983             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3984         StChain.push_back(DAG.getStore(
3985             Chain, dl, EOp, BasePtr, ST->getPointerInfo().getWithOffset(Offset),
3986             MinAlign(Align, Offset), MMOFlags, AAInfo));
3987         StWidth -= NewVTWidth;
3988         Offset += Increment;
3989         Idx += NumVTElts;
3990         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
3991                               DAG.getConstant(Increment, dl,
3992                                               BasePtr.getValueType()));
3993       } while (StWidth != 0 && StWidth >= NewVTWidth);
3994     } else {
3995       // Cast the vector to the scalar type we can store.
3996       unsigned NumElts = ValWidth / NewVTWidth;
3997       EVT NewVecVT = EVT::getVectorVT(*DAG.getContext(), NewVT, NumElts);
3998       SDValue VecOp = DAG.getNode(ISD::BITCAST, dl, NewVecVT, ValOp);
3999       // Readjust index position based on new vector type.
4000       Idx = Idx * ValEltWidth / NewVTWidth;
4001       do {
4002         SDValue EOp = DAG.getNode(
4003             ISD::EXTRACT_VECTOR_ELT, dl, NewVT, VecOp,
4004             DAG.getConstant(Idx++, dl,
4005                             TLI.getVectorIdxTy(DAG.getDataLayout())));
4006         StChain.push_back(DAG.getStore(
4007             Chain, dl, EOp, BasePtr, ST->getPointerInfo().getWithOffset(Offset),
4008             MinAlign(Align, Offset), MMOFlags, AAInfo));
4009         StWidth -= NewVTWidth;
4010         Offset += Increment;
4011         BasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(), BasePtr,
4012                               DAG.getConstant(Increment, dl,
4013                                               BasePtr.getValueType()));
4014       } while (StWidth != 0 && StWidth >= NewVTWidth);
4015       // Restore index back to be relative to the original widen element type.
4016       Idx = Idx * NewVTWidth / ValEltWidth;
4017     }
4018   }
4019 }
4020
4021 void
4022 DAGTypeLegalizer::GenWidenVectorTruncStores(SmallVectorImpl<SDValue> &StChain,
4023                                             StoreSDNode *ST) {
4024   // For extension loads, it may not be more efficient to truncate the vector
4025   // and then store it. Instead, we extract each element and then store it.
4026   SDValue Chain = ST->getChain();
4027   SDValue BasePtr = ST->getBasePtr();
4028   unsigned Align = ST->getAlignment();
4029   MachineMemOperand::Flags MMOFlags = ST->getMemOperand()->getFlags();
4030   AAMDNodes AAInfo = ST->getAAInfo();
4031   SDValue ValOp = GetWidenedVector(ST->getValue());
4032   SDLoc dl(ST);
4033
4034   EVT StVT = ST->getMemoryVT();
4035   EVT ValVT = ValOp.getValueType();
4036
4037   // It must be true that the wide vector type is bigger than where we need to
4038   // store.
4039   assert(StVT.isVector() && ValOp.getValueType().isVector());
4040   assert(StVT.bitsLT(ValOp.getValueType()));
4041
4042   // For truncating stores, we can not play the tricks of chopping legal vector
4043   // types and bitcast it to the right type. Instead, we unroll the store.
4044   EVT StEltVT  = StVT.getVectorElementType();
4045   EVT ValEltVT = ValVT.getVectorElementType();
4046   unsigned Increment = ValEltVT.getSizeInBits() / 8;
4047   unsigned NumElts = StVT.getVectorNumElements();
4048   SDValue EOp = DAG.getNode(
4049       ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
4050       DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4051   StChain.push_back(DAG.getTruncStore(Chain, dl, EOp, BasePtr,
4052                                       ST->getPointerInfo(), StEltVT, Align,
4053                                       MMOFlags, AAInfo));
4054   unsigned Offset = Increment;
4055   for (unsigned i=1; i < NumElts; ++i, Offset += Increment) {
4056     SDValue NewBasePtr = DAG.getNode(ISD::ADD, dl, BasePtr.getValueType(),
4057                                      BasePtr,
4058                                      DAG.getConstant(Offset, dl,
4059                                                      BasePtr.getValueType()));
4060     SDValue EOp = DAG.getNode(
4061         ISD::EXTRACT_VECTOR_ELT, dl, ValEltVT, ValOp,
4062         DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4063     StChain.push_back(DAG.getTruncStore(
4064         Chain, dl, EOp, NewBasePtr, ST->getPointerInfo().getWithOffset(Offset),
4065         StEltVT, MinAlign(Align, Offset), MMOFlags, AAInfo));
4066   }
4067 }
4068
4069 /// Modifies a vector input (widen or narrows) to a vector of NVT.  The
4070 /// input vector must have the same element type as NVT.
4071 /// FillWithZeroes specifies that the vector should be widened with zeroes.
4072 SDValue DAGTypeLegalizer::ModifyToType(SDValue InOp, EVT NVT,
4073                                        bool FillWithZeroes) {
4074   // Note that InOp might have been widened so it might already have
4075   // the right width or it might need be narrowed.
4076   EVT InVT = InOp.getValueType();
4077   assert(InVT.getVectorElementType() == NVT.getVectorElementType() &&
4078          "input and widen element type must match");
4079   SDLoc dl(InOp);
4080
4081   // Check if InOp already has the right width.
4082   if (InVT == NVT)
4083     return InOp;
4084
4085   unsigned InNumElts = InVT.getVectorNumElements();
4086   unsigned WidenNumElts = NVT.getVectorNumElements();
4087   if (WidenNumElts > InNumElts && WidenNumElts % InNumElts == 0) {
4088     unsigned NumConcat = WidenNumElts / InNumElts;
4089     SmallVector<SDValue, 16> Ops(NumConcat);
4090     SDValue FillVal = FillWithZeroes ? DAG.getConstant(0, dl, InVT) :
4091       DAG.getUNDEF(InVT);
4092     Ops[0] = InOp;
4093     for (unsigned i = 1; i != NumConcat; ++i)
4094       Ops[i] = FillVal;
4095
4096     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, Ops);
4097   }
4098
4099   if (WidenNumElts < InNumElts && InNumElts % WidenNumElts)
4100     return DAG.getNode(
4101         ISD::EXTRACT_SUBVECTOR, dl, NVT, InOp,
4102         DAG.getConstant(0, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4103
4104   // Fall back to extract and build.
4105   SmallVector<SDValue, 16> Ops(WidenNumElts);
4106   EVT EltVT = NVT.getVectorElementType();
4107   unsigned MinNumElts = std::min(WidenNumElts, InNumElts);
4108   unsigned Idx;
4109   for (Idx = 0; Idx < MinNumElts; ++Idx)
4110     Ops[Idx] = DAG.getNode(
4111         ISD::EXTRACT_VECTOR_ELT, dl, EltVT, InOp,
4112         DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4113
4114   SDValue FillVal = FillWithZeroes ? DAG.getConstant(0, dl, EltVT) :
4115     DAG.getUNDEF(EltVT);
4116   for ( ; Idx < WidenNumElts; ++Idx)
4117     Ops[Idx] = FillVal;
4118   return DAG.getBuildVector(NVT, dl, Ops);
4119 }