1 //===-- LegalizeTypesExpand.cpp - Expansion for LegalizeTypes -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements expansion support for LegalizeTypes. Expansion is the
11 // act of changing a computation in an invalid type to be a computation in
12 // multiple registers of a smaller type. For example, implementing i64
13 // arithmetic in two i32 registers (as is often needed on 32-bit targets, for
16 //===----------------------------------------------------------------------===//
18 #include "LegalizeTypes.h"
19 #include "llvm/Constants.h"
22 //===----------------------------------------------------------------------===//
24 //===----------------------------------------------------------------------===//
26 /// ExpandResult - This method is called when the specified result of the
27 /// specified node is found to need expansion. At this point, the node may also
28 /// have invalid operands or may have other results that need promotion, we just
29 /// know that (at least) one result needs expansion.
30 void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) {
31 DEBUG(cerr << "Expand node result: "; N->dump(&DAG); cerr << "\n");
33 Lo = Hi = SDOperand();
35 // See if the target wants to custom expand this node.
36 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
37 TargetLowering::Custom) {
38 // If the target wants to, allow it to lower this itself.
39 if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) {
40 // Everything that once used N now uses P. We are guaranteed that the
41 // result value types of N and the result value types of P match.
42 ReplaceNodeWith(N, P);
47 switch (N->getOpcode()) {
50 cerr << "ExpandResult #" << ResNo << ": ";
51 N->dump(&DAG); cerr << "\n";
53 assert(0 && "Do not know how to expand the result of this operator!");
56 case ISD::UNDEF: ExpandResult_UNDEF(N, Lo, Hi); break;
57 case ISD::Constant: ExpandResult_Constant(N, Lo, Hi); break;
58 case ISD::BUILD_PAIR: ExpandResult_BUILD_PAIR(N, Lo, Hi); break;
59 case ISD::MERGE_VALUES: ExpandResult_MERGE_VALUES(N, Lo, Hi); break;
60 case ISD::ANY_EXTEND: ExpandResult_ANY_EXTEND(N, Lo, Hi); break;
61 case ISD::ZERO_EXTEND: ExpandResult_ZERO_EXTEND(N, Lo, Hi); break;
62 case ISD::SIGN_EXTEND: ExpandResult_SIGN_EXTEND(N, Lo, Hi); break;
63 case ISD::AssertZext: ExpandResult_AssertZext(N, Lo, Hi); break;
64 case ISD::TRUNCATE: ExpandResult_TRUNCATE(N, Lo, Hi); break;
65 case ISD::BIT_CONVERT: ExpandResult_BIT_CONVERT(N, Lo, Hi); break;
66 case ISD::SIGN_EXTEND_INREG: ExpandResult_SIGN_EXTEND_INREG(N, Lo, Hi); break;
67 case ISD::FP_TO_SINT: ExpandResult_FP_TO_SINT(N, Lo, Hi); break;
68 case ISD::FP_TO_UINT: ExpandResult_FP_TO_UINT(N, Lo, Hi); break;
69 case ISD::LOAD: ExpandResult_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
73 case ISD::XOR: ExpandResult_Logical(N, Lo, Hi); break;
74 case ISD::BSWAP: ExpandResult_BSWAP(N, Lo, Hi); break;
76 case ISD::SUB: ExpandResult_ADDSUB(N, Lo, Hi); break;
78 case ISD::SUBC: ExpandResult_ADDSUBC(N, Lo, Hi); break;
80 case ISD::SUBE: ExpandResult_ADDSUBE(N, Lo, Hi); break;
81 case ISD::SELECT: ExpandResult_SELECT(N, Lo, Hi); break;
82 case ISD::SELECT_CC: ExpandResult_SELECT_CC(N, Lo, Hi); break;
83 case ISD::MUL: ExpandResult_MUL(N, Lo, Hi); break;
84 case ISD::SDIV: ExpandResult_SDIV(N, Lo, Hi); break;
85 case ISD::SREM: ExpandResult_SREM(N, Lo, Hi); break;
86 case ISD::UDIV: ExpandResult_UDIV(N, Lo, Hi); break;
87 case ISD::UREM: ExpandResult_UREM(N, Lo, Hi); break;
90 case ISD::SRL: ExpandResult_Shift(N, Lo, Hi); break;
92 case ISD::CTLZ: ExpandResult_CTLZ(N, Lo, Hi); break;
93 case ISD::CTPOP: ExpandResult_CTPOP(N, Lo, Hi); break;
94 case ISD::CTTZ: ExpandResult_CTTZ(N, Lo, Hi); break;
96 case ISD::EXTRACT_VECTOR_ELT:
97 ExpandResult_EXTRACT_VECTOR_ELT(N, Lo, Hi);
101 // If Lo/Hi is null, the sub-method took care of registering results etc.
103 SetExpandedOp(SDOperand(N, ResNo), Lo, Hi);
106 void DAGTypeLegalizer::ExpandResult_UNDEF(SDNode *N,
107 SDOperand &Lo, SDOperand &Hi) {
108 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
109 Lo = Hi = DAG.getNode(ISD::UNDEF, NVT);
112 void DAGTypeLegalizer::ExpandResult_Constant(SDNode *N,
113 SDOperand &Lo, SDOperand &Hi) {
114 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
115 unsigned NBitWidth = MVT::getSizeInBits(NVT);
116 const APInt &Cst = cast<ConstantSDNode>(N)->getAPIntValue();
117 Lo = DAG.getConstant(APInt(Cst).trunc(NBitWidth), NVT);
118 Hi = DAG.getConstant(Cst.lshr(NBitWidth).trunc(NBitWidth), NVT);
121 void DAGTypeLegalizer::ExpandResult_BUILD_PAIR(SDNode *N,
122 SDOperand &Lo, SDOperand &Hi) {
123 // Return the operands.
124 Lo = N->getOperand(0);
125 Hi = N->getOperand(1);
128 void DAGTypeLegalizer::ExpandResult_MERGE_VALUES(SDNode *N,
129 SDOperand &Lo, SDOperand &Hi) {
130 // A MERGE_VALUES node can produce any number of values. We know that the
131 // first illegal one needs to be expanded into Lo/Hi.
134 // The string of legal results gets turns into the input operands, which have
136 for (i = 0; isTypeLegal(N->getValueType(i)); ++i)
137 ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
139 // The first illegal result must be the one that needs to be expanded.
140 GetExpandedOp(N->getOperand(i), Lo, Hi);
142 // Legalize the rest of the results into the input operands whether they are
144 unsigned e = N->getNumValues();
145 for (++i; i != e; ++i)
146 ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
149 void DAGTypeLegalizer::ExpandResult_ANY_EXTEND(SDNode *N,
150 SDOperand &Lo, SDOperand &Hi) {
151 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
152 SDOperand Op = N->getOperand(0);
153 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
154 // The low part is any extension of the input (which degenerates to a copy).
155 Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Op);
156 Hi = DAG.getNode(ISD::UNDEF, NVT); // The high part is undefined.
158 // For example, extension of an i48 to an i64. The operand type necessarily
159 // promotes to the result type, so will end up being expanded too.
160 assert(getTypeAction(Op.getValueType()) == Promote &&
161 "Only know how to promote this result!");
162 SDOperand Res = GetPromotedOp(Op);
163 assert(Res.getValueType() == N->getValueType(0) &&
164 "Operand over promoted?");
165 // Split the promoted operand. This will simplify when it is expanded.
166 SplitInteger(Res, Lo, Hi);
170 void DAGTypeLegalizer::ExpandResult_ZERO_EXTEND(SDNode *N,
171 SDOperand &Lo, SDOperand &Hi) {
172 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
173 SDOperand Op = N->getOperand(0);
174 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
175 // The low part is zero extension of the input (which degenerates to a copy).
176 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, N->getOperand(0));
177 Hi = DAG.getConstant(0, NVT); // The high part is just a zero.
179 // For example, extension of an i48 to an i64. The operand type necessarily
180 // promotes to the result type, so will end up being expanded too.
181 assert(getTypeAction(Op.getValueType()) == Promote &&
182 "Only know how to promote this result!");
183 SDOperand Res = GetPromotedOp(Op);
184 assert(Res.getValueType() == N->getValueType(0) &&
185 "Operand over promoted?");
186 // Split the promoted operand. This will simplify when it is expanded.
187 SplitInteger(Res, Lo, Hi);
188 unsigned ExcessBits =
189 MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT);
190 Hi = DAG.getZeroExtendInReg(Hi, MVT::getIntegerType(ExcessBits));
194 void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N,
195 SDOperand &Lo, SDOperand &Hi) {
196 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
197 SDOperand Op = N->getOperand(0);
198 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
199 // The low part is sign extension of the input (which degenerates to a copy).
200 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, N->getOperand(0));
201 // The high part is obtained by SRA'ing all but one of the bits of low part.
202 unsigned LoSize = MVT::getSizeInBits(NVT);
203 Hi = DAG.getNode(ISD::SRA, NVT, Lo,
204 DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
206 // For example, extension of an i48 to an i64. The operand type necessarily
207 // promotes to the result type, so will end up being expanded too.
208 assert(getTypeAction(Op.getValueType()) == Promote &&
209 "Only know how to promote this result!");
210 SDOperand Res = GetPromotedOp(Op);
211 assert(Res.getValueType() == N->getValueType(0) &&
212 "Operand over promoted?");
213 // Split the promoted operand. This will simplify when it is expanded.
214 SplitInteger(Res, Lo, Hi);
215 unsigned ExcessBits =
216 MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT);
217 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
218 DAG.getValueType(MVT::getIntegerType(ExcessBits)));
222 void DAGTypeLegalizer::ExpandResult_AssertZext(SDNode *N,
223 SDOperand &Lo, SDOperand &Hi) {
224 GetExpandedOp(N->getOperand(0), Lo, Hi);
225 MVT::ValueType NVT = Lo.getValueType();
226 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
227 unsigned NVTBits = MVT::getSizeInBits(NVT);
228 unsigned EVTBits = MVT::getSizeInBits(EVT);
230 if (NVTBits < EVTBits) {
231 Hi = DAG.getNode(ISD::AssertZext, NVT, Hi,
232 DAG.getValueType(MVT::getIntegerType(EVTBits - NVTBits)));
234 Lo = DAG.getNode(ISD::AssertZext, NVT, Lo, DAG.getValueType(EVT));
235 // The high part must be zero, make it explicit.
236 Hi = DAG.getConstant(0, NVT);
240 void DAGTypeLegalizer::ExpandResult_TRUNCATE(SDNode *N,
241 SDOperand &Lo, SDOperand &Hi) {
242 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
243 Lo = DAG.getNode(ISD::TRUNCATE, NVT, N->getOperand(0));
244 Hi = DAG.getNode(ISD::SRL, N->getOperand(0).getValueType(), N->getOperand(0),
245 DAG.getConstant(MVT::getSizeInBits(NVT),
246 TLI.getShiftAmountTy()));
247 Hi = DAG.getNode(ISD::TRUNCATE, NVT, Hi);
250 void DAGTypeLegalizer::ExpandResult_BIT_CONVERT(SDNode *N,
251 SDOperand &Lo, SDOperand &Hi) {
252 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
253 SDOperand InOp = N->getOperand(0);
254 MVT::ValueType InVT = InOp.getValueType();
256 // Handle some special cases efficiently.
257 switch (getTypeAction(InVT)) {
259 assert(false && "Unknown type action!");
264 // Convert the expanded pieces of the input.
265 GetExpandedOp(InOp, Lo, Hi);
266 Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Lo);
267 Hi = DAG.getNode(ISD::BIT_CONVERT, NVT, Hi);
270 // Convert the integer operand instead.
271 SplitInteger(GetIntegerOp(InOp), Lo, Hi);
272 Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Lo);
273 Hi = DAG.getNode(ISD::BIT_CONVERT, NVT, Hi);
276 // Convert the split parts of the input if it was split in two.
277 GetSplitOp(InOp, Lo, Hi);
278 if (Lo.getValueType() == Hi.getValueType()) {
279 if (TLI.isBigEndian())
281 Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Lo);
282 Hi = DAG.getNode(ISD::BIT_CONVERT, NVT, Hi);
287 // Convert the element instead.
288 SplitInteger(BitConvertToInteger(GetScalarizedOp(InOp)), Lo, Hi);
289 Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Lo);
290 Hi = DAG.getNode(ISD::BIT_CONVERT, NVT, Hi);
294 // Lower the bit-convert to a store/load from the stack, then expand the load.
295 SDOperand Op = CreateStackStoreLoad(InOp, N->getValueType(0));
296 ExpandResult_LOAD(cast<LoadSDNode>(Op.Val), Lo, Hi);
299 void DAGTypeLegalizer::
300 ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
301 GetExpandedOp(N->getOperand(0), Lo, Hi);
302 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
304 if (MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(Lo.getValueType())) {
305 // sext_inreg the low part if needed.
306 Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, Lo.getValueType(), Lo,
309 // The high part gets the sign extension from the lo-part. This handles
310 // things like sextinreg V:i64 from i8.
311 Hi = DAG.getNode(ISD::SRA, Hi.getValueType(), Lo,
312 DAG.getConstant(MVT::getSizeInBits(Hi.getValueType())-1,
313 TLI.getShiftAmountTy()));
315 // For example, extension of an i48 to an i64. Leave the low part alone,
316 // sext_inreg the high part.
317 unsigned ExcessBits =
318 MVT::getSizeInBits(EVT) - MVT::getSizeInBits(Lo.getValueType());
319 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
320 DAG.getValueType(MVT::getIntegerType(ExcessBits)));
324 void DAGTypeLegalizer::ExpandResult_FP_TO_SINT(SDNode *N, SDOperand &Lo,
326 MVT::ValueType VT = N->getValueType(0);
327 SDOperand Op = N->getOperand(0);
328 RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
329 if (VT == MVT::i64) {
330 if (Op.getValueType() == MVT::f32)
331 LC = RTLIB::FPTOSINT_F32_I64;
332 else if (Op.getValueType() == MVT::f64)
333 LC = RTLIB::FPTOSINT_F64_I64;
334 else if (Op.getValueType() == MVT::f80)
335 LC = RTLIB::FPTOSINT_F80_I64;
336 else if (Op.getValueType() == MVT::ppcf128)
337 LC = RTLIB::FPTOSINT_PPCF128_I64;
338 } else if (VT == MVT::i128) {
339 if (Op.getValueType() == MVT::f32)
340 LC = RTLIB::FPTOSINT_F32_I128;
341 else if (Op.getValueType() == MVT::f64)
342 LC = RTLIB::FPTOSINT_F64_I128;
343 else if (Op.getValueType() == MVT::f80)
344 LC = RTLIB::FPTOSINT_F80_I128;
345 else if (Op.getValueType() == MVT::ppcf128)
346 LC = RTLIB::FPTOSINT_PPCF128_I128;
348 assert(0 && "Unexpected fp-to-sint conversion!");
350 SplitInteger(MakeLibCall(LC, VT, &Op, 1, true/*sign irrelevant*/), Lo, Hi);
353 void DAGTypeLegalizer::ExpandResult_FP_TO_UINT(SDNode *N, SDOperand &Lo,
355 MVT::ValueType VT = N->getValueType(0);
356 SDOperand Op = N->getOperand(0);
357 RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
358 if (VT == MVT::i64) {
359 if (Op.getValueType() == MVT::f32)
360 LC = RTLIB::FPTOUINT_F32_I64;
361 else if (Op.getValueType() == MVT::f64)
362 LC = RTLIB::FPTOUINT_F64_I64;
363 else if (Op.getValueType() == MVT::f80)
364 LC = RTLIB::FPTOUINT_F80_I64;
365 else if (Op.getValueType() == MVT::ppcf128)
366 LC = RTLIB::FPTOUINT_PPCF128_I64;
367 } else if (VT == MVT::i128) {
368 if (Op.getValueType() == MVT::f32)
369 LC = RTLIB::FPTOUINT_F32_I128;
370 else if (Op.getValueType() == MVT::f64)
371 LC = RTLIB::FPTOUINT_F64_I128;
372 else if (Op.getValueType() == MVT::f80)
373 LC = RTLIB::FPTOUINT_F80_I128;
374 else if (Op.getValueType() == MVT::ppcf128)
375 LC = RTLIB::FPTOUINT_PPCF128_I128;
377 assert(0 && "Unexpected fp-to-uint conversion!");
379 SplitInteger(MakeLibCall(LC, VT, &Op, 1, false/*sign irrelevant*/), Lo, Hi);
382 void DAGTypeLegalizer::ExpandResult_LOAD(LoadSDNode *N,
383 SDOperand &Lo, SDOperand &Hi) {
384 // FIXME: Add support for indexed loads.
385 MVT::ValueType VT = N->getValueType(0);
386 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
387 SDOperand Ch = N->getChain(); // Legalize the chain.
388 SDOperand Ptr = N->getBasePtr(); // Legalize the pointer.
389 ISD::LoadExtType ExtType = N->getExtensionType();
390 int SVOffset = N->getSrcValueOffset();
391 unsigned Alignment = N->getAlignment();
392 bool isVolatile = N->isVolatile();
394 assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!");
396 if (ExtType == ISD::NON_EXTLOAD) {
397 Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
398 isVolatile, Alignment);
399 // Increment the pointer to the other half.
400 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
401 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
402 DAG.getIntPtrConstant(IncrementSize));
403 Hi = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
404 isVolatile, MinAlign(Alignment, IncrementSize));
406 // Build a factor node to remember that this load is independent of the
408 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
411 // Handle endianness of the load.
412 if (TLI.isBigEndian())
414 } else if (MVT::getSizeInBits(N->getMemoryVT()) <= MVT::getSizeInBits(NVT)) {
415 MVT::ValueType EVT = N->getMemoryVT();
417 Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset, EVT,
418 isVolatile, Alignment);
420 // Remember the chain.
423 if (ExtType == ISD::SEXTLOAD) {
424 // The high part is obtained by SRA'ing all but one of the bits of the
426 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
427 Hi = DAG.getNode(ISD::SRA, NVT, Lo,
428 DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
429 } else if (ExtType == ISD::ZEXTLOAD) {
430 // The high part is just a zero.
431 Hi = DAG.getConstant(0, NVT);
433 assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
434 // The high part is undefined.
435 Hi = DAG.getNode(ISD::UNDEF, NVT);
437 } else if (TLI.isLittleEndian()) {
438 // Little-endian - low bits are at low addresses.
439 Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
440 isVolatile, Alignment);
442 unsigned ExcessBits =
443 MVT::getSizeInBits(N->getMemoryVT()) - MVT::getSizeInBits(NVT);
444 MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits);
446 // Increment the pointer to the other half.
447 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
448 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
449 DAG.getIntPtrConstant(IncrementSize));
450 Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(),
451 SVOffset+IncrementSize, NEVT,
452 isVolatile, MinAlign(Alignment, IncrementSize));
454 // Build a factor node to remember that this load is independent of the
456 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
459 // Big-endian - high bits are at low addresses. Favor aligned loads at
460 // the cost of some bit-fiddling.
461 MVT::ValueType EVT = N->getMemoryVT();
462 unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8;
463 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
464 unsigned ExcessBits = (EBytes - IncrementSize)*8;
466 // Load both the high bits and maybe some of the low bits.
467 Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
468 MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits),
469 isVolatile, Alignment);
471 // Increment the pointer to the other half.
472 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
473 DAG.getIntPtrConstant(IncrementSize));
474 // Load the rest of the low bits.
475 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Ch, Ptr, N->getSrcValue(),
476 SVOffset+IncrementSize, MVT::getIntegerType(ExcessBits),
477 isVolatile, MinAlign(Alignment, IncrementSize));
479 // Build a factor node to remember that this load is independent of the
481 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
484 if (ExcessBits < MVT::getSizeInBits(NVT)) {
485 // Transfer low bits from the bottom of Hi to the top of Lo.
486 Lo = DAG.getNode(ISD::OR, NVT, Lo,
487 DAG.getNode(ISD::SHL, NVT, Hi,
488 DAG.getConstant(ExcessBits,
489 TLI.getShiftAmountTy())));
490 // Move high bits to the right position in Hi.
491 Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, NVT, Hi,
492 DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits,
493 TLI.getShiftAmountTy()));
497 // Legalized the chain result - switch anything that used the old chain to
499 ReplaceValueWith(SDOperand(N, 1), Ch);
502 void DAGTypeLegalizer::ExpandResult_Logical(SDNode *N,
503 SDOperand &Lo, SDOperand &Hi) {
504 SDOperand LL, LH, RL, RH;
505 GetExpandedOp(N->getOperand(0), LL, LH);
506 GetExpandedOp(N->getOperand(1), RL, RH);
507 Lo = DAG.getNode(N->getOpcode(), LL.getValueType(), LL, RL);
508 Hi = DAG.getNode(N->getOpcode(), LL.getValueType(), LH, RH);
511 void DAGTypeLegalizer::ExpandResult_BSWAP(SDNode *N,
512 SDOperand &Lo, SDOperand &Hi) {
513 GetExpandedOp(N->getOperand(0), Hi, Lo); // Note swapped operands.
514 Lo = DAG.getNode(ISD::BSWAP, Lo.getValueType(), Lo);
515 Hi = DAG.getNode(ISD::BSWAP, Hi.getValueType(), Hi);
518 void DAGTypeLegalizer::ExpandResult_SELECT(SDNode *N,
519 SDOperand &Lo, SDOperand &Hi) {
520 SDOperand LL, LH, RL, RH;
521 GetExpandedOp(N->getOperand(1), LL, LH);
522 GetExpandedOp(N->getOperand(2), RL, RH);
523 Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LL, RL);
524 Hi = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LH, RH);
527 void DAGTypeLegalizer::ExpandResult_SELECT_CC(SDNode *N,
528 SDOperand &Lo, SDOperand &Hi) {
529 SDOperand LL, LH, RL, RH;
530 GetExpandedOp(N->getOperand(2), LL, LH);
531 GetExpandedOp(N->getOperand(3), RL, RH);
532 Lo = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
533 N->getOperand(1), LL, RL, N->getOperand(4));
534 Hi = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
535 N->getOperand(1), LH, RH, N->getOperand(4));
538 void DAGTypeLegalizer::ExpandResult_ADDSUB(SDNode *N,
539 SDOperand &Lo, SDOperand &Hi) {
540 // Expand the subcomponents.
541 SDOperand LHSL, LHSH, RHSL, RHSH;
542 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
543 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
544 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
545 SDOperand LoOps[2] = { LHSL, RHSL };
546 SDOperand HiOps[3] = { LHSH, RHSH };
548 if (N->getOpcode() == ISD::ADD) {
549 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
550 HiOps[2] = Lo.getValue(1);
551 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
553 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
554 HiOps[2] = Lo.getValue(1);
555 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
559 void DAGTypeLegalizer::ExpandResult_ADDSUBC(SDNode *N,
560 SDOperand &Lo, SDOperand &Hi) {
561 // Expand the subcomponents.
562 SDOperand LHSL, LHSH, RHSL, RHSH;
563 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
564 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
565 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
566 SDOperand LoOps[2] = { LHSL, RHSL };
567 SDOperand HiOps[3] = { LHSH, RHSH };
569 if (N->getOpcode() == ISD::ADDC) {
570 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
571 HiOps[2] = Lo.getValue(1);
572 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
574 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
575 HiOps[2] = Lo.getValue(1);
576 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
579 // Legalized the flag result - switch anything that used the old flag to
581 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
584 void DAGTypeLegalizer::ExpandResult_ADDSUBE(SDNode *N,
585 SDOperand &Lo, SDOperand &Hi) {
586 // Expand the subcomponents.
587 SDOperand LHSL, LHSH, RHSL, RHSH;
588 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
589 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
590 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
591 SDOperand LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
592 SDOperand HiOps[3] = { LHSH, RHSH };
594 Lo = DAG.getNode(N->getOpcode(), VTList, LoOps, 3);
595 HiOps[2] = Lo.getValue(1);
596 Hi = DAG.getNode(N->getOpcode(), VTList, HiOps, 3);
598 // Legalized the flag result - switch anything that used the old flag to
600 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
603 void DAGTypeLegalizer::ExpandResult_MUL(SDNode *N,
604 SDOperand &Lo, SDOperand &Hi) {
605 MVT::ValueType VT = N->getValueType(0);
606 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
608 bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT);
609 bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT);
610 bool HasSMUL_LOHI = TLI.isOperationLegal(ISD::SMUL_LOHI, NVT);
611 bool HasUMUL_LOHI = TLI.isOperationLegal(ISD::UMUL_LOHI, NVT);
612 if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
613 SDOperand LL, LH, RL, RH;
614 GetExpandedOp(N->getOperand(0), LL, LH);
615 GetExpandedOp(N->getOperand(1), RL, RH);
616 unsigned OuterBitSize = MVT::getSizeInBits(VT);
617 unsigned BitSize = MVT::getSizeInBits(NVT);
618 unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
619 unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
621 if (DAG.MaskedValueIsZero(N->getOperand(0),
622 APInt::getHighBitsSet(OuterBitSize, LHSSB)) &&
623 DAG.MaskedValueIsZero(N->getOperand(1),
624 APInt::getHighBitsSet(OuterBitSize, RHSSB))) {
625 // The inputs are both zero-extended.
627 // We can emit a umul_lohi.
628 Lo = DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
629 Hi = SDOperand(Lo.Val, 1);
633 // We can emit a mulhu+mul.
634 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
635 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
639 if (LHSSB > BitSize && RHSSB > BitSize) {
640 // The input values are both sign-extended.
642 // We can emit a smul_lohi.
643 Lo = DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
644 Hi = SDOperand(Lo.Val, 1);
648 // We can emit a mulhs+mul.
649 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
650 Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
655 // Lo,Hi = umul LHS, RHS.
656 SDOperand UMulLOHI = DAG.getNode(ISD::UMUL_LOHI,
657 DAG.getVTList(NVT, NVT), LL, RL);
659 Hi = UMulLOHI.getValue(1);
660 RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
661 LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
662 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
663 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
668 // If nothing else, we can make a libcall.
669 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
670 SplitInteger(MakeLibCall(RTLIB::MUL_I64, VT, Ops, 2, true/*sign irrelevant*/),
674 void DAGTypeLegalizer::ExpandResult_SDIV(SDNode *N,
675 SDOperand &Lo, SDOperand &Hi) {
676 assert(N->getValueType(0) == MVT::i64 && "Unsupported sdiv!");
677 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
678 SplitInteger(MakeLibCall(RTLIB::SDIV_I64, N->getValueType(0), Ops, 2, true),
682 void DAGTypeLegalizer::ExpandResult_SREM(SDNode *N,
683 SDOperand &Lo, SDOperand &Hi) {
684 assert(N->getValueType(0) == MVT::i64 && "Unsupported srem!");
685 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
686 SplitInteger(MakeLibCall(RTLIB::SREM_I64, N->getValueType(0), Ops, 2, true),
690 void DAGTypeLegalizer::ExpandResult_UDIV(SDNode *N,
691 SDOperand &Lo, SDOperand &Hi) {
692 assert(N->getValueType(0) == MVT::i64 && "Unsupported udiv!");
693 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
694 SplitInteger(MakeLibCall(RTLIB::UDIV_I64, N->getValueType(0), Ops, 2, false),
698 void DAGTypeLegalizer::ExpandResult_UREM(SDNode *N,
699 SDOperand &Lo, SDOperand &Hi) {
700 assert(N->getValueType(0) == MVT::i64 && "Unsupported urem!");
701 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
702 SplitInteger(MakeLibCall(RTLIB::UREM_I64, N->getValueType(0), Ops, 2, false),
706 void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N,
707 SDOperand &Lo, SDOperand &Hi) {
708 MVT::ValueType VT = N->getValueType(0);
710 // If we can emit an efficient shift operation, do so now. Check to see if
711 // the RHS is a constant.
712 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
713 return ExpandShiftByConstant(N, CN->getValue(), Lo, Hi);
715 // If we can determine that the high bit of the shift is zero or one, even if
716 // the low bits are variable, emit this shift in an optimized form.
717 if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
720 // If this target supports shift_PARTS, use it. First, map to the _PARTS opc.
722 if (N->getOpcode() == ISD::SHL) {
723 PartsOpc = ISD::SHL_PARTS;
724 } else if (N->getOpcode() == ISD::SRL) {
725 PartsOpc = ISD::SRL_PARTS;
727 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
728 PartsOpc = ISD::SRA_PARTS;
731 // Next check to see if the target supports this SHL_PARTS operation or if it
732 // will custom expand it.
733 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
734 TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
735 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
736 Action == TargetLowering::Custom) {
737 // Expand the subcomponents.
738 SDOperand LHSL, LHSH;
739 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
741 SDOperand Ops[] = { LHSL, LHSH, N->getOperand(1) };
742 MVT::ValueType VT = LHSL.getValueType();
743 Lo = DAG.getNode(PartsOpc, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3);
748 // Otherwise, emit a libcall.
749 assert(VT == MVT::i64 && "Unsupported shift!");
753 if (N->getOpcode() == ISD::SHL) {
755 isSigned = false; /*sign irrelevant*/
756 } else if (N->getOpcode() == ISD::SRL) {
760 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
765 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
766 SplitInteger(MakeLibCall(LC, VT, Ops, 2, isSigned), Lo, Hi);
769 void DAGTypeLegalizer::ExpandResult_CTLZ(SDNode *N,
770 SDOperand &Lo, SDOperand &Hi) {
771 // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
772 GetExpandedOp(N->getOperand(0), Lo, Hi);
773 MVT::ValueType NVT = Lo.getValueType();
775 SDOperand HiNotZero = DAG.getSetCC(TLI.getSetCCResultType(Hi), Hi,
776 DAG.getConstant(0, NVT), ISD::SETNE);
778 SDOperand LoLZ = DAG.getNode(ISD::CTLZ, NVT, Lo);
779 SDOperand HiLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
781 Lo = DAG.getNode(ISD::SELECT, NVT, HiNotZero, HiLZ,
782 DAG.getNode(ISD::ADD, NVT, LoLZ,
783 DAG.getConstant(MVT::getSizeInBits(NVT), NVT)));
784 Hi = DAG.getConstant(0, NVT);
787 void DAGTypeLegalizer::ExpandResult_CTPOP(SDNode *N,
788 SDOperand &Lo, SDOperand &Hi) {
789 // ctpop(HiLo) -> ctpop(Hi)+ctpop(Lo)
790 GetExpandedOp(N->getOperand(0), Lo, Hi);
791 MVT::ValueType NVT = Lo.getValueType();
792 Lo = DAG.getNode(ISD::ADD, NVT, DAG.getNode(ISD::CTPOP, NVT, Lo),
793 DAG.getNode(ISD::CTPOP, NVT, Hi));
794 Hi = DAG.getConstant(0, NVT);
797 void DAGTypeLegalizer::ExpandResult_CTTZ(SDNode *N,
798 SDOperand &Lo, SDOperand &Hi) {
799 // cttz (HiLo) -> Lo != 0 ? cttz(Lo) : (cttz(Hi)+32)
800 GetExpandedOp(N->getOperand(0), Lo, Hi);
801 MVT::ValueType NVT = Lo.getValueType();
803 SDOperand LoNotZero = DAG.getSetCC(TLI.getSetCCResultType(Lo), Lo,
804 DAG.getConstant(0, NVT), ISD::SETNE);
806 SDOperand LoLZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
807 SDOperand HiLZ = DAG.getNode(ISD::CTTZ, NVT, Hi);
809 Lo = DAG.getNode(ISD::SELECT, NVT, LoNotZero, LoLZ,
810 DAG.getNode(ISD::ADD, NVT, HiLZ,
811 DAG.getConstant(MVT::getSizeInBits(NVT), NVT)));
812 Hi = DAG.getConstant(0, NVT);
815 void DAGTypeLegalizer::ExpandResult_EXTRACT_VECTOR_ELT(SDNode *N,
818 SDOperand OldVec = N->getOperand(0);
819 unsigned OldElts = MVT::getVectorNumElements(OldVec.getValueType());
821 // Convert to a vector of the expanded element type, for example
822 // <2 x i64> -> <4 x i32>.
823 MVT::ValueType OldVT = N->getValueType(0);
824 MVT::ValueType NewVT = TLI.getTypeToTransformTo(OldVT);
825 assert(MVT::getSizeInBits(OldVT) == 2 * MVT::getSizeInBits(NewVT) &&
826 "Do not know how to handle this expansion!");
828 SDOperand NewVec = DAG.getNode(ISD::BIT_CONVERT,
829 MVT::getVectorType(NewVT, 2 * OldElts),
832 // Extract the elements at 2 * Idx and 2 * Idx + 1 from the new vector.
833 SDOperand Idx = N->getOperand(1);
835 // Make sure the type of Idx is big enough to hold the new values.
836 if (MVT::getSizeInBits(Idx.getValueType()) <
837 MVT::getSizeInBits(TLI.getPointerTy()))
838 Idx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), Idx);
840 Idx = DAG.getNode(ISD::ADD, Idx.getValueType(), Idx, Idx);
841 Lo = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, NewVT, NewVec, Idx);
843 Idx = DAG.getNode(ISD::ADD, Idx.getValueType(), Idx,
844 DAG.getConstant(1, Idx.getValueType()));
845 Hi = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, NewVT, NewVec, Idx);
847 if (TLI.isBigEndian())
851 /// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
852 /// and the shift amount is a constant 'Amt'. Expand the operation.
853 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt,
854 SDOperand &Lo, SDOperand &Hi) {
855 // Expand the incoming operand to be shifted, so that we have its parts
857 GetExpandedOp(N->getOperand(0), InL, InH);
859 MVT::ValueType NVT = InL.getValueType();
860 unsigned VTBits = MVT::getSizeInBits(N->getValueType(0));
861 unsigned NVTBits = MVT::getSizeInBits(NVT);
862 MVT::ValueType ShTy = N->getOperand(1).getValueType();
864 if (N->getOpcode() == ISD::SHL) {
866 Lo = Hi = DAG.getConstant(0, NVT);
867 } else if (Amt > NVTBits) {
868 Lo = DAG.getConstant(0, NVT);
869 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy));
870 } else if (Amt == NVTBits) {
871 Lo = DAG.getConstant(0, NVT);
874 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt, ShTy));
875 Hi = DAG.getNode(ISD::OR, NVT,
876 DAG.getNode(ISD::SHL, NVT, InH,
877 DAG.getConstant(Amt, ShTy)),
878 DAG.getNode(ISD::SRL, NVT, InL,
879 DAG.getConstant(NVTBits-Amt, ShTy)));
884 if (N->getOpcode() == ISD::SRL) {
886 Lo = DAG.getConstant(0, NVT);
887 Hi = DAG.getConstant(0, NVT);
888 } else if (Amt > NVTBits) {
889 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt-NVTBits,ShTy));
890 Hi = DAG.getConstant(0, NVT);
891 } else if (Amt == NVTBits) {
893 Hi = DAG.getConstant(0, NVT);
895 Lo = DAG.getNode(ISD::OR, NVT,
896 DAG.getNode(ISD::SRL, NVT, InL,
897 DAG.getConstant(Amt, ShTy)),
898 DAG.getNode(ISD::SHL, NVT, InH,
899 DAG.getConstant(NVTBits-Amt, ShTy)));
900 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt, ShTy));
905 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
907 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
908 DAG.getConstant(NVTBits-1, ShTy));
909 } else if (Amt > NVTBits) {
910 Lo = DAG.getNode(ISD::SRA, NVT, InH,
911 DAG.getConstant(Amt-NVTBits, ShTy));
912 Hi = DAG.getNode(ISD::SRA, NVT, InH,
913 DAG.getConstant(NVTBits-1, ShTy));
914 } else if (Amt == NVTBits) {
916 Hi = DAG.getNode(ISD::SRA, NVT, InH,
917 DAG.getConstant(NVTBits-1, ShTy));
919 Lo = DAG.getNode(ISD::OR, NVT,
920 DAG.getNode(ISD::SRL, NVT, InL,
921 DAG.getConstant(Amt, ShTy)),
922 DAG.getNode(ISD::SHL, NVT, InH,
923 DAG.getConstant(NVTBits-Amt, ShTy)));
924 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Amt, ShTy));
928 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
929 /// this shift based on knowledge of the high bit of the shift amount. If we
930 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
932 bool DAGTypeLegalizer::
933 ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
934 SDOperand Amt = N->getOperand(1);
935 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
936 MVT::ValueType ShTy = Amt.getValueType();
937 MVT::ValueType ShBits = MVT::getSizeInBits(ShTy);
938 unsigned NVTBits = MVT::getSizeInBits(NVT);
939 assert(isPowerOf2_32(NVTBits) &&
940 "Expanded integer type size not a power of two!");
942 APInt HighBitMask = APInt::getHighBitsSet(ShBits, ShBits - Log2_32(NVTBits));
943 APInt KnownZero, KnownOne;
944 DAG.ComputeMaskedBits(N->getOperand(1), HighBitMask, KnownZero, KnownOne);
946 // If we don't know anything about the high bits, exit.
947 if (((KnownZero|KnownOne) & HighBitMask) == 0)
950 // Get the incoming operand to be shifted.
952 GetExpandedOp(N->getOperand(0), InL, InH);
954 // If we know that any of the high bits of the shift amount are one, then we
955 // can do this as a couple of simple shifts.
956 if (KnownOne.intersects(HighBitMask)) {
957 // Mask out the high bit, which we know is set.
958 Amt = DAG.getNode(ISD::AND, ShTy, Amt,
959 DAG.getConstant(~HighBitMask, ShTy));
961 switch (N->getOpcode()) {
962 default: assert(0 && "Unknown shift");
964 Lo = DAG.getConstant(0, NVT); // Low part is zero.
965 Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part.
968 Hi = DAG.getConstant(0, NVT); // Hi part is zero.
969 Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part.
972 Hi = DAG.getNode(ISD::SRA, NVT, InH, // Sign extend high part.
973 DAG.getConstant(NVTBits-1, ShTy));
974 Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part.
979 // If we know that all of the high bits of the shift amount are zero, then we
980 // can do this as a couple of simple shifts.
981 if ((KnownZero & HighBitMask) == HighBitMask) {
983 SDOperand Amt2 = DAG.getNode(ISD::SUB, ShTy,
984 DAG.getConstant(NVTBits, ShTy),
987 switch (N->getOpcode()) {
988 default: assert(0 && "Unknown shift");
989 case ISD::SHL: Op1 = ISD::SHL; Op2 = ISD::SRL; break;
991 case ISD::SRA: Op1 = ISD::SRL; Op2 = ISD::SHL; break;
994 Lo = DAG.getNode(N->getOpcode(), NVT, InL, Amt);
995 Hi = DAG.getNode(ISD::OR, NVT,
996 DAG.getNode(Op1, NVT, InH, Amt),
997 DAG.getNode(Op2, NVT, InL, Amt2));
1005 //===----------------------------------------------------------------------===//
1006 // Operand Expansion
1007 //===----------------------------------------------------------------------===//
1009 /// ExpandOperand - This method is called when the specified operand of the
1010 /// specified node is found to need expansion. At this point, all of the result
1011 /// types of the node are known to be legal, but other operands of the node may
1012 /// need promotion or expansion as well as the specified one.
1013 bool DAGTypeLegalizer::ExpandOperand(SDNode *N, unsigned OpNo) {
1014 DEBUG(cerr << "Expand node operand: "; N->dump(&DAG); cerr << "\n");
1015 SDOperand Res(0, 0);
1017 if (TLI.getOperationAction(N->getOpcode(), N->getOperand(OpNo).getValueType())
1018 == TargetLowering::Custom)
1019 Res = TLI.LowerOperation(SDOperand(N, 0), DAG);
1022 switch (N->getOpcode()) {
1025 cerr << "ExpandOperand Op #" << OpNo << ": ";
1026 N->dump(&DAG); cerr << "\n";
1028 assert(0 && "Do not know how to expand this operator's operand!");
1031 case ISD::TRUNCATE: Res = ExpandOperand_TRUNCATE(N); break;
1032 case ISD::BIT_CONVERT: Res = ExpandOperand_BIT_CONVERT(N); break;
1034 case ISD::SINT_TO_FP:
1035 Res = ExpandOperand_SINT_TO_FP(N->getOperand(0), N->getValueType(0));
1037 case ISD::UINT_TO_FP:
1038 Res = ExpandOperand_UINT_TO_FP(N->getOperand(0), N->getValueType(0));
1040 case ISD::EXTRACT_ELEMENT: Res = ExpandOperand_EXTRACT_ELEMENT(N); break;
1042 case ISD::BR_CC: Res = ExpandOperand_BR_CC(N); break;
1043 case ISD::SETCC: Res = ExpandOperand_SETCC(N); break;
1046 Res = ExpandOperand_STORE(cast<StoreSDNode>(N), OpNo);
1049 case ISD::BUILD_VECTOR: Res = ExpandOperand_BUILD_VECTOR(N); break;
1053 // If the result is null, the sub-method took care of registering results etc.
1054 if (!Res.Val) return false;
1055 // If the result is N, the sub-method updated N in place. Check to see if any
1056 // operands are new, and if so, mark them.
1058 // Mark N as new and remark N and its operands. This allows us to correctly
1059 // revisit N if it needs another step of promotion and allows us to visit
1060 // any new operands to N.
1065 assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1066 "Invalid operand expansion");
1068 ReplaceValueWith(SDOperand(N, 0), Res);
1072 SDOperand DAGTypeLegalizer::ExpandOperand_TRUNCATE(SDNode *N) {
1074 GetExpandedOp(N->getOperand(0), InL, InH);
1075 // Just truncate the low part of the source.
1076 return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), InL);
1079 SDOperand DAGTypeLegalizer::ExpandOperand_BIT_CONVERT(SDNode *N) {
1080 if (MVT::isVector(N->getValueType(0))) {
1081 // An illegal integer type is being converted to a legal vector type.
1082 // Make a two element vector out of the expanded parts and convert that
1083 // instead, but only if the new vector type is legal (otherwise there
1084 // is no point, and it might create expansion loops). For example, on
1085 // x86 this turns v1i64 = BIT_CONVERT i64 into v1i64 = BIT_CONVERT v2i32.
1086 MVT::ValueType OVT = N->getOperand(0).getValueType();
1087 MVT::ValueType NVT = MVT::getVectorType(TLI.getTypeToTransformTo(OVT), 2);
1089 if (isTypeLegal(NVT)) {
1091 GetExpandedOp(N->getOperand(0), Parts[0], Parts[1]);
1093 if (TLI.isBigEndian())
1094 std::swap(Parts[0], Parts[1]);
1096 SDOperand Vec = DAG.getNode(ISD::BUILD_VECTOR, NVT, Parts, 2);
1097 return DAG.getNode(ISD::BIT_CONVERT, N->getValueType(0), Vec);
1101 // Otherwise, store to a temporary and load out again as the new type.
1102 return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
1105 SDOperand DAGTypeLegalizer::ExpandOperand_SINT_TO_FP(SDOperand Source,
1106 MVT::ValueType DestTy) {
1107 // We know the destination is legal, but that the input needs to be expanded.
1108 MVT::ValueType SourceVT = Source.getValueType();
1110 // Check to see if the target has a custom way to lower this. If so, use it.
1111 switch (TLI.getOperationAction(ISD::SINT_TO_FP, SourceVT)) {
1112 default: assert(0 && "This action not implemented for this operation!");
1113 case TargetLowering::Legal:
1114 case TargetLowering::Expand:
1115 break; // This case is handled below.
1116 case TargetLowering::Custom:
1117 SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
1119 if (NV.Val) return NV;
1120 break; // The target lowered this.
1123 RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
1124 if (SourceVT == MVT::i64) {
1125 if (DestTy == MVT::f32)
1126 LC = RTLIB::SINTTOFP_I64_F32;
1128 assert(DestTy == MVT::f64 && "Unknown fp value type!");
1129 LC = RTLIB::SINTTOFP_I64_F64;
1131 } else if (SourceVT == MVT::i128) {
1132 if (DestTy == MVT::f32)
1133 LC = RTLIB::SINTTOFP_I128_F32;
1134 else if (DestTy == MVT::f64)
1135 LC = RTLIB::SINTTOFP_I128_F64;
1136 else if (DestTy == MVT::f80)
1137 LC = RTLIB::SINTTOFP_I128_F80;
1139 assert(DestTy == MVT::ppcf128 && "Unknown fp value type!");
1140 LC = RTLIB::SINTTOFP_I128_PPCF128;
1143 assert(0 && "Unknown int value type!");
1146 assert(LC != RTLIB::UNKNOWN_LIBCALL &&
1147 "Don't know how to expand this SINT_TO_FP!");
1148 return MakeLibCall(LC, DestTy, &Source, 1, true);
1151 SDOperand DAGTypeLegalizer::ExpandOperand_UINT_TO_FP(SDOperand Source,
1152 MVT::ValueType DestTy) {
1153 // We know the destination is legal, but that the input needs to be expanded.
1154 assert(getTypeAction(Source.getValueType()) == Expand &&
1155 "This is not an expansion!");
1157 // If this is unsigned, and not supported, first perform the conversion to
1158 // signed, then adjust the result if the sign bit is set.
1159 SDOperand SignedConv = ExpandOperand_SINT_TO_FP(Source, DestTy);
1161 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
1162 // incoming integer is set. To handle this, we dynamically test to see if
1163 // it is set, and, if so, add a fudge factor.
1165 GetExpandedOp(Source, Lo, Hi);
1167 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultType(Hi), Hi,
1168 DAG.getConstant(0, Hi.getValueType()),
1170 SDOperand Zero = DAG.getIntPtrConstant(0), Four = DAG.getIntPtrConstant(4);
1171 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
1172 SignSet, Four, Zero);
1173 uint64_t FF = 0x5f800000ULL;
1174 if (TLI.isLittleEndian()) FF <<= 32;
1175 Constant *FudgeFactor = ConstantInt::get((Type*)Type::Int64Ty, FF);
1177 SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
1178 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
1179 SDOperand FudgeInReg;
1180 if (DestTy == MVT::f32)
1181 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0);
1182 else if (MVT::getSizeInBits(DestTy) > MVT::getSizeInBits(MVT::f32))
1183 // FIXME: Avoid the extend by construction the right constantpool?
1184 FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, DestTy, DAG.getEntryNode(),
1185 CPIdx, NULL, 0, MVT::f32);
1187 assert(0 && "Unexpected conversion");
1189 return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
1192 SDOperand DAGTypeLegalizer::ExpandOperand_EXTRACT_ELEMENT(SDNode *N) {
1194 GetExpandedOp(N->getOperand(0), Lo, Hi);
1195 return cast<ConstantSDNode>(N->getOperand(1))->getValue() ? Hi : Lo;
1198 SDOperand DAGTypeLegalizer::ExpandOperand_BR_CC(SDNode *N) {
1199 SDOperand NewLHS = N->getOperand(2), NewRHS = N->getOperand(3);
1200 ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(1))->get();
1201 ExpandSetCCOperands(NewLHS, NewRHS, CCCode);
1203 // If ExpandSetCCOperands returned a scalar, we need to compare the result
1204 // against zero to select between true and false values.
1205 if (NewRHS.Val == 0) {
1206 NewRHS = DAG.getConstant(0, NewLHS.getValueType());
1207 CCCode = ISD::SETNE;
1210 // Update N to have the operands specified.
1211 return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0),
1212 DAG.getCondCode(CCCode), NewLHS, NewRHS,
1216 SDOperand DAGTypeLegalizer::ExpandOperand_SETCC(SDNode *N) {
1217 SDOperand NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
1218 ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
1219 ExpandSetCCOperands(NewLHS, NewRHS, CCCode);
1221 // If ExpandSetCCOperands returned a scalar, use it.
1222 if (NewRHS.Val == 0) return NewLHS;
1224 // Otherwise, update N to have the operands specified.
1225 return DAG.UpdateNodeOperands(SDOperand(N, 0), NewLHS, NewRHS,
1226 DAG.getCondCode(CCCode));
1229 /// ExpandSetCCOperands - Expand the operands of a comparison. This code is
1230 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
1231 void DAGTypeLegalizer::ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS,
1232 ISD::CondCode &CCCode) {
1233 SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
1234 GetExpandedOp(NewLHS, LHSLo, LHSHi);
1235 GetExpandedOp(NewRHS, RHSLo, RHSHi);
1237 MVT::ValueType VT = NewLHS.getValueType();
1238 if (VT == MVT::ppcf128) {
1239 // FIXME: This generated code sucks. We want to generate
1240 // FCMP crN, hi1, hi2
1242 // FCMP crN, lo1, lo2
1243 // The following can be improved, but not that much.
1244 SDOperand Tmp1, Tmp2, Tmp3;
1245 Tmp1 = DAG.getSetCC(TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi, ISD::SETEQ);
1246 Tmp2 = DAG.getSetCC(TLI.getSetCCResultType(LHSLo), LHSLo, RHSLo, CCCode);
1247 Tmp3 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
1248 Tmp1 = DAG.getSetCC(TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi, ISD::SETNE);
1249 Tmp2 = DAG.getSetCC(TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi, CCCode);
1250 Tmp1 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
1251 NewLHS = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp3);
1252 NewRHS = SDOperand(); // LHS is the result, not a compare.
1256 if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
1258 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
1259 if (RHSCST->isAllOnesValue()) {
1260 // Equality comparison to -1.
1261 NewLHS = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
1266 NewLHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
1267 NewRHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
1268 NewLHS = DAG.getNode(ISD::OR, NewLHS.getValueType(), NewLHS, NewRHS);
1269 NewRHS = DAG.getConstant(0, NewLHS.getValueType());
1273 // If this is a comparison of the sign bit, just look at the top part.
1275 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
1276 if ((CCCode == ISD::SETLT && CST->isNullValue()) || // X < 0
1277 (CCCode == ISD::SETGT && CST->isAllOnesValue())) { // X > -1
1283 // FIXME: This generated code sucks.
1284 ISD::CondCode LowCC;
1286 default: assert(0 && "Unknown integer setcc!");
1288 case ISD::SETULT: LowCC = ISD::SETULT; break;
1290 case ISD::SETUGT: LowCC = ISD::SETUGT; break;
1292 case ISD::SETULE: LowCC = ISD::SETULE; break;
1294 case ISD::SETUGE: LowCC = ISD::SETUGE; break;
1297 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison
1298 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands
1299 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
1301 // NOTE: on targets without efficient SELECT of bools, we can always use
1302 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
1303 TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, false, true, NULL);
1304 SDOperand Tmp1, Tmp2;
1305 Tmp1 = TLI.SimplifySetCC(TLI.getSetCCResultType(LHSLo), LHSLo, RHSLo, LowCC,
1306 false, DagCombineInfo);
1308 Tmp1 = DAG.getSetCC(TLI.getSetCCResultType(LHSLo), LHSLo, RHSLo, LowCC);
1309 Tmp2 = TLI.SimplifySetCC(TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi,
1310 CCCode, false, DagCombineInfo);
1312 Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi,
1313 DAG.getCondCode(CCCode));
1315 ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.Val);
1316 ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.Val);
1317 if ((Tmp1C && Tmp1C->isNullValue()) ||
1318 (Tmp2C && Tmp2C->isNullValue() &&
1319 (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
1320 CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
1321 (Tmp2C && Tmp2C->getAPIntValue() == 1 &&
1322 (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
1323 CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
1324 // low part is known false, returns high part.
1325 // For LE / GE, if high part is known false, ignore the low part.
1326 // For LT / GT, if high part is known true, ignore the low part.
1328 NewRHS = SDOperand();
1332 NewLHS = TLI.SimplifySetCC(TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi,
1333 ISD::SETEQ, false, DagCombineInfo);
1335 NewLHS = DAG.getSetCC(TLI.getSetCCResultType(LHSHi), LHSHi, RHSHi,
1337 NewLHS = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
1338 NewLHS, Tmp1, Tmp2);
1339 NewRHS = SDOperand();
1342 SDOperand DAGTypeLegalizer::ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo) {
1343 // FIXME: Add support for indexed stores.
1344 assert(OpNo == 1 && "Can only expand the stored value so far");
1346 MVT::ValueType VT = N->getOperand(1).getValueType();
1347 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1348 SDOperand Ch = N->getChain();
1349 SDOperand Ptr = N->getBasePtr();
1350 int SVOffset = N->getSrcValueOffset();
1351 unsigned Alignment = N->getAlignment();
1352 bool isVolatile = N->isVolatile();
1355 assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!");
1357 if (!N->isTruncatingStore()) {
1358 unsigned IncrementSize = 0;
1359 GetExpandedOp(N->getValue(), Lo, Hi);
1360 IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
1362 if (TLI.isBigEndian())
1365 Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(),
1366 SVOffset, isVolatile, Alignment);
1368 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1369 DAG.getIntPtrConstant(IncrementSize));
1370 assert(isTypeLegal(Ptr.getValueType()) && "Pointers must be legal!");
1371 Hi = DAG.getStore(Ch, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
1372 isVolatile, MinAlign(Alignment, IncrementSize));
1373 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1374 } else if (MVT::getSizeInBits(N->getMemoryVT()) <= MVT::getSizeInBits(NVT)) {
1375 GetExpandedOp(N->getValue(), Lo, Hi);
1376 return DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
1377 N->getMemoryVT(), isVolatile, Alignment);
1378 } else if (TLI.isLittleEndian()) {
1379 // Little-endian - low bits are at low addresses.
1380 GetExpandedOp(N->getValue(), Lo, Hi);
1382 Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
1383 isVolatile, Alignment);
1385 unsigned ExcessBits =
1386 MVT::getSizeInBits(N->getMemoryVT()) - MVT::getSizeInBits(NVT);
1387 MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits);
1389 // Increment the pointer to the other half.
1390 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
1391 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1392 DAG.getIntPtrConstant(IncrementSize));
1393 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1394 SVOffset+IncrementSize, NEVT,
1395 isVolatile, MinAlign(Alignment, IncrementSize));
1396 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1398 // Big-endian - high bits are at low addresses. Favor aligned stores at
1399 // the cost of some bit-fiddling.
1400 GetExpandedOp(N->getValue(), Lo, Hi);
1402 MVT::ValueType EVT = N->getMemoryVT();
1403 unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8;
1404 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
1405 unsigned ExcessBits = (EBytes - IncrementSize)*8;
1406 MVT::ValueType HiVT =
1407 MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits);
1409 if (ExcessBits < MVT::getSizeInBits(NVT)) {
1410 // Transfer high bits from the top of Lo to the bottom of Hi.
1411 Hi = DAG.getNode(ISD::SHL, NVT, Hi,
1412 DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits,
1413 TLI.getShiftAmountTy()));
1414 Hi = DAG.getNode(ISD::OR, NVT, Hi,
1415 DAG.getNode(ISD::SRL, NVT, Lo,
1416 DAG.getConstant(ExcessBits,
1417 TLI.getShiftAmountTy())));
1420 // Store both the high bits and maybe some of the low bits.
1421 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1422 SVOffset, HiVT, isVolatile, Alignment);
1424 // Increment the pointer to the other half.
1425 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1426 DAG.getIntPtrConstant(IncrementSize));
1427 // Store the lowest ExcessBits bits in the second half.
1428 Lo = DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(),
1429 SVOffset+IncrementSize,
1430 MVT::getIntegerType(ExcessBits),
1431 isVolatile, MinAlign(Alignment, IncrementSize));
1432 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1436 SDOperand DAGTypeLegalizer::ExpandOperand_BUILD_VECTOR(SDNode *N) {
1437 // The vector type is legal but the element type needs expansion.
1438 MVT::ValueType VecVT = N->getValueType(0);
1439 unsigned NumElts = MVT::getVectorNumElements(VecVT);
1440 MVT::ValueType OldVT = N->getOperand(0).getValueType();
1441 MVT::ValueType NewVT = TLI.getTypeToTransformTo(OldVT);
1443 assert(MVT::getSizeInBits(OldVT) == 2 * MVT::getSizeInBits(NewVT) &&
1444 "Do not know how to expand this operand!");
1446 // Build a vector of twice the length out of the expanded elements.
1447 // For example <2 x i64> -> <4 x i32>.
1448 std::vector<SDOperand> NewElts;
1449 NewElts.reserve(NumElts*2);
1451 for (unsigned i = 0; i < NumElts; ++i) {
1453 GetExpandedOp(N->getOperand(i), Lo, Hi);
1454 if (TLI.isBigEndian())
1456 NewElts.push_back(Lo);
1457 NewElts.push_back(Hi);
1460 SDOperand NewVec = DAG.getNode(ISD::BUILD_VECTOR,
1461 MVT::getVectorType(NewVT, NewElts.size()),
1462 &NewElts[0], NewElts.size());
1464 // Convert the new vector to the old vector type.
1465 return DAG.getNode(ISD::BIT_CONVERT, VecVT, NewVec);