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