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