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 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 NVT = TLI.getTypeToTransformTo(N->getValueType(0));
115 unsigned NBitWidth = NVT.getSizeInBits();
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 NVT = TLI.getTypeToTransformTo(N->getValueType(0));
152 SDOperand Op = N->getOperand(0);
153 if (Op.getValueType().bitsLE(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 NVT = TLI.getTypeToTransformTo(N->getValueType(0));
173 SDOperand Op = N->getOperand(0);
174 if (Op.getValueType().bitsLE(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 Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
190 Hi = DAG.getZeroExtendInReg(Hi, MVT::getIntegerVT(ExcessBits));
194 void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N,
195 SDOperand &Lo, SDOperand &Hi) {
196 MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
197 SDOperand Op = N->getOperand(0);
198 if (Op.getValueType().bitsLE(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 = NVT.getSizeInBits();
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 Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
217 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
218 DAG.getValueType(MVT::getIntegerVT(ExcessBits)));
222 void DAGTypeLegalizer::ExpandResult_AssertZext(SDNode *N,
223 SDOperand &Lo, SDOperand &Hi) {
224 GetExpandedOp(N->getOperand(0), Lo, Hi);
225 MVT NVT = Lo.getValueType();
226 MVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
227 unsigned NVTBits = NVT.getSizeInBits();
228 unsigned EVTBits = EVT.getSizeInBits();
230 if (NVTBits < EVTBits) {
231 Hi = DAG.getNode(ISD::AssertZext, NVT, Hi,
232 DAG.getValueType(MVT::getIntegerVT(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 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(NVT.getSizeInBits(),
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 NVT = TLI.getTypeToTransformTo(N->getValueType(0));
253 SDOperand InOp = N->getOperand(0);
254 MVT 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 EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
304 if (EVT.bitsLE(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(Hi.getValueType().getSizeInBits()-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 EVT.getSizeInBits() - Lo.getValueType().getSizeInBits();
319 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
320 DAG.getValueType(MVT::getIntegerVT(ExcessBits)));
324 void DAGTypeLegalizer::ExpandResult_FP_TO_SINT(SDNode *N, SDOperand &Lo,
326 MVT 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 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 VT = N->getValueType(0);
386 MVT 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(!(NVT.getSizeInBits() & 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 = NVT.getSizeInBits()/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 (N->getMemoryVT().bitsLE(NVT)) {
415 MVT 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 = Lo.getValueType().getSizeInBits();
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 N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
444 MVT NEVT = MVT::getIntegerVT(ExcessBits);
446 // Increment the pointer to the other half.
447 unsigned IncrementSize = NVT.getSizeInBits()/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 EVT = N->getMemoryVT();
462 unsigned EBytes = EVT.getStoreSizeInBits()/8;
463 unsigned IncrementSize = NVT.getSizeInBits()/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::getIntegerVT(EVT.getSizeInBits() - 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,
477 MVT::getIntegerVT(ExcessBits),
478 isVolatile, MinAlign(Alignment, IncrementSize));
480 // Build a factor node to remember that this load is independent of the
482 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
485 if (ExcessBits < NVT.getSizeInBits()) {
486 // Transfer low bits from the bottom of Hi to the top of Lo.
487 Lo = DAG.getNode(ISD::OR, NVT, Lo,
488 DAG.getNode(ISD::SHL, NVT, Hi,
489 DAG.getConstant(ExcessBits,
490 TLI.getShiftAmountTy())));
491 // Move high bits to the right position in Hi.
492 Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, NVT, Hi,
493 DAG.getConstant(NVT.getSizeInBits() - ExcessBits,
494 TLI.getShiftAmountTy()));
498 // Legalized the chain result - switch anything that used the old chain to
500 ReplaceValueWith(SDOperand(N, 1), Ch);
503 void DAGTypeLegalizer::ExpandResult_Logical(SDNode *N,
504 SDOperand &Lo, SDOperand &Hi) {
505 SDOperand LL, LH, RL, RH;
506 GetExpandedOp(N->getOperand(0), LL, LH);
507 GetExpandedOp(N->getOperand(1), RL, RH);
508 Lo = DAG.getNode(N->getOpcode(), LL.getValueType(), LL, RL);
509 Hi = DAG.getNode(N->getOpcode(), LL.getValueType(), LH, RH);
512 void DAGTypeLegalizer::ExpandResult_BSWAP(SDNode *N,
513 SDOperand &Lo, SDOperand &Hi) {
514 GetExpandedOp(N->getOperand(0), Hi, Lo); // Note swapped operands.
515 Lo = DAG.getNode(ISD::BSWAP, Lo.getValueType(), Lo);
516 Hi = DAG.getNode(ISD::BSWAP, Hi.getValueType(), Hi);
519 void DAGTypeLegalizer::ExpandResult_SELECT(SDNode *N,
520 SDOperand &Lo, SDOperand &Hi) {
521 SDOperand LL, LH, RL, RH;
522 GetExpandedOp(N->getOperand(1), LL, LH);
523 GetExpandedOp(N->getOperand(2), RL, RH);
524 Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LL, RL);
525 Hi = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LH, RH);
528 void DAGTypeLegalizer::ExpandResult_SELECT_CC(SDNode *N,
529 SDOperand &Lo, SDOperand &Hi) {
530 SDOperand LL, LH, RL, RH;
531 GetExpandedOp(N->getOperand(2), LL, LH);
532 GetExpandedOp(N->getOperand(3), RL, RH);
533 Lo = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
534 N->getOperand(1), LL, RL, N->getOperand(4));
535 Hi = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
536 N->getOperand(1), LH, RH, N->getOperand(4));
539 void DAGTypeLegalizer::ExpandResult_ADDSUB(SDNode *N,
540 SDOperand &Lo, SDOperand &Hi) {
541 // Expand the subcomponents.
542 SDOperand LHSL, LHSH, RHSL, RHSH;
543 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
544 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
545 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
546 SDOperand LoOps[2] = { LHSL, RHSL };
547 SDOperand HiOps[3] = { LHSH, RHSH };
549 if (N->getOpcode() == ISD::ADD) {
550 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
551 HiOps[2] = Lo.getValue(1);
552 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
554 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
555 HiOps[2] = Lo.getValue(1);
556 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
560 void DAGTypeLegalizer::ExpandResult_ADDSUBC(SDNode *N,
561 SDOperand &Lo, SDOperand &Hi) {
562 // Expand the subcomponents.
563 SDOperand LHSL, LHSH, RHSL, RHSH;
564 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
565 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
566 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
567 SDOperand LoOps[2] = { LHSL, RHSL };
568 SDOperand HiOps[3] = { LHSH, RHSH };
570 if (N->getOpcode() == ISD::ADDC) {
571 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
572 HiOps[2] = Lo.getValue(1);
573 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
575 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
576 HiOps[2] = Lo.getValue(1);
577 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
580 // Legalized the flag result - switch anything that used the old flag to
582 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
585 void DAGTypeLegalizer::ExpandResult_ADDSUBE(SDNode *N,
586 SDOperand &Lo, SDOperand &Hi) {
587 // Expand the subcomponents.
588 SDOperand LHSL, LHSH, RHSL, RHSH;
589 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
590 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
591 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
592 SDOperand LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
593 SDOperand HiOps[3] = { LHSH, RHSH };
595 Lo = DAG.getNode(N->getOpcode(), VTList, LoOps, 3);
596 HiOps[2] = Lo.getValue(1);
597 Hi = DAG.getNode(N->getOpcode(), VTList, HiOps, 3);
599 // Legalized the flag result - switch anything that used the old flag to
601 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
604 void DAGTypeLegalizer::ExpandResult_MUL(SDNode *N,
605 SDOperand &Lo, SDOperand &Hi) {
606 MVT VT = N->getValueType(0);
607 MVT NVT = TLI.getTypeToTransformTo(VT);
609 bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT);
610 bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT);
611 bool HasSMUL_LOHI = TLI.isOperationLegal(ISD::SMUL_LOHI, NVT);
612 bool HasUMUL_LOHI = TLI.isOperationLegal(ISD::UMUL_LOHI, NVT);
613 if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
614 SDOperand LL, LH, RL, RH;
615 GetExpandedOp(N->getOperand(0), LL, LH);
616 GetExpandedOp(N->getOperand(1), RL, RH);
617 unsigned OuterBitSize = VT.getSizeInBits();
618 unsigned BitSize = NVT.getSizeInBits();
619 unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
620 unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
622 if (DAG.MaskedValueIsZero(N->getOperand(0),
623 APInt::getHighBitsSet(OuterBitSize, LHSSB)) &&
624 DAG.MaskedValueIsZero(N->getOperand(1),
625 APInt::getHighBitsSet(OuterBitSize, RHSSB))) {
626 // The inputs are both zero-extended.
628 // We can emit a umul_lohi.
629 Lo = DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
630 Hi = SDOperand(Lo.Val, 1);
634 // We can emit a mulhu+mul.
635 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
636 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
640 if (LHSSB > BitSize && RHSSB > BitSize) {
641 // The input values are both sign-extended.
643 // We can emit a smul_lohi.
644 Lo = DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
645 Hi = SDOperand(Lo.Val, 1);
649 // We can emit a mulhs+mul.
650 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
651 Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
656 // Lo,Hi = umul LHS, RHS.
657 SDOperand UMulLOHI = DAG.getNode(ISD::UMUL_LOHI,
658 DAG.getVTList(NVT, NVT), LL, RL);
660 Hi = UMulLOHI.getValue(1);
661 RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
662 LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
663 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
664 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
669 // If nothing else, we can make a libcall.
670 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
671 SplitInteger(MakeLibCall(RTLIB::MUL_I64, VT, Ops, 2, true/*sign irrelevant*/),
675 void DAGTypeLegalizer::ExpandResult_SDIV(SDNode *N,
676 SDOperand &Lo, SDOperand &Hi) {
677 assert(N->getValueType(0) == MVT::i64 && "Unsupported sdiv!");
678 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
679 SplitInteger(MakeLibCall(RTLIB::SDIV_I64, N->getValueType(0), Ops, 2, true),
683 void DAGTypeLegalizer::ExpandResult_SREM(SDNode *N,
684 SDOperand &Lo, SDOperand &Hi) {
685 assert(N->getValueType(0) == MVT::i64 && "Unsupported srem!");
686 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
687 SplitInteger(MakeLibCall(RTLIB::SREM_I64, N->getValueType(0), Ops, 2, true),
691 void DAGTypeLegalizer::ExpandResult_UDIV(SDNode *N,
692 SDOperand &Lo, SDOperand &Hi) {
693 assert(N->getValueType(0) == MVT::i64 && "Unsupported udiv!");
694 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
695 SplitInteger(MakeLibCall(RTLIB::UDIV_I64, N->getValueType(0), Ops, 2, false),
699 void DAGTypeLegalizer::ExpandResult_UREM(SDNode *N,
700 SDOperand &Lo, SDOperand &Hi) {
701 assert(N->getValueType(0) == MVT::i64 && "Unsupported urem!");
702 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
703 SplitInteger(MakeLibCall(RTLIB::UREM_I64, N->getValueType(0), Ops, 2, false),
707 void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N,
708 SDOperand &Lo, SDOperand &Hi) {
709 MVT VT = N->getValueType(0);
711 // If we can emit an efficient shift operation, do so now. Check to see if
712 // the RHS is a constant.
713 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
714 return ExpandShiftByConstant(N, CN->getValue(), Lo, Hi);
716 // If we can determine that the high bit of the shift is zero or one, even if
717 // the low bits are variable, emit this shift in an optimized form.
718 if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
721 // If this target supports shift_PARTS, use it. First, map to the _PARTS opc.
723 if (N->getOpcode() == ISD::SHL) {
724 PartsOpc = ISD::SHL_PARTS;
725 } else if (N->getOpcode() == ISD::SRL) {
726 PartsOpc = ISD::SRL_PARTS;
728 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
729 PartsOpc = ISD::SRA_PARTS;
732 // Next check to see if the target supports this SHL_PARTS operation or if it
733 // will custom expand it.
734 MVT NVT = TLI.getTypeToTransformTo(VT);
735 TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
736 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
737 Action == TargetLowering::Custom) {
738 // Expand the subcomponents.
739 SDOperand LHSL, LHSH;
740 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
742 SDOperand Ops[] = { LHSL, LHSH, N->getOperand(1) };
743 MVT VT = LHSL.getValueType();
744 Lo = DAG.getNode(PartsOpc, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3);
749 // Otherwise, emit a libcall.
750 assert(VT == MVT::i64 && "Unsupported shift!");
754 if (N->getOpcode() == ISD::SHL) {
756 isSigned = false; /*sign irrelevant*/
757 } else if (N->getOpcode() == ISD::SRL) {
761 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
766 SDOperand Ops[2] = { N->getOperand(0), N->getOperand(1) };
767 SplitInteger(MakeLibCall(LC, VT, Ops, 2, isSigned), Lo, Hi);
770 void DAGTypeLegalizer::ExpandResult_CTLZ(SDNode *N,
771 SDOperand &Lo, SDOperand &Hi) {
772 // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
773 GetExpandedOp(N->getOperand(0), Lo, Hi);
774 MVT NVT = Lo.getValueType();
776 SDOperand HiNotZero = DAG.getSetCC(TLI.getSetCCResultType(Hi), Hi,
777 DAG.getConstant(0, NVT), ISD::SETNE);
779 SDOperand LoLZ = DAG.getNode(ISD::CTLZ, NVT, Lo);
780 SDOperand HiLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
782 Lo = DAG.getNode(ISD::SELECT, NVT, HiNotZero, HiLZ,
783 DAG.getNode(ISD::ADD, NVT, LoLZ,
784 DAG.getConstant(NVT.getSizeInBits(), NVT)));
785 Hi = DAG.getConstant(0, NVT);
788 void DAGTypeLegalizer::ExpandResult_CTPOP(SDNode *N,
789 SDOperand &Lo, SDOperand &Hi) {
790 // ctpop(HiLo) -> ctpop(Hi)+ctpop(Lo)
791 GetExpandedOp(N->getOperand(0), Lo, Hi);
792 MVT NVT = Lo.getValueType();
793 Lo = DAG.getNode(ISD::ADD, NVT, DAG.getNode(ISD::CTPOP, NVT, Lo),
794 DAG.getNode(ISD::CTPOP, NVT, Hi));
795 Hi = DAG.getConstant(0, NVT);
798 void DAGTypeLegalizer::ExpandResult_CTTZ(SDNode *N,
799 SDOperand &Lo, SDOperand &Hi) {
800 // cttz (HiLo) -> Lo != 0 ? cttz(Lo) : (cttz(Hi)+32)
801 GetExpandedOp(N->getOperand(0), Lo, Hi);
802 MVT NVT = Lo.getValueType();
804 SDOperand LoNotZero = DAG.getSetCC(TLI.getSetCCResultType(Lo), Lo,
805 DAG.getConstant(0, NVT), ISD::SETNE);
807 SDOperand LoLZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
808 SDOperand HiLZ = DAG.getNode(ISD::CTTZ, NVT, Hi);
810 Lo = DAG.getNode(ISD::SELECT, NVT, LoNotZero, LoLZ,
811 DAG.getNode(ISD::ADD, NVT, HiLZ,
812 DAG.getConstant(NVT.getSizeInBits(), NVT)));
813 Hi = DAG.getConstant(0, NVT);
816 void DAGTypeLegalizer::ExpandResult_EXTRACT_VECTOR_ELT(SDNode *N,
819 SDOperand OldVec = N->getOperand(0);
820 unsigned OldElts = OldVec.getValueType().getVectorNumElements();
822 // Convert to a vector of the expanded element type, for example
823 // <2 x i64> -> <4 x i32>.
824 MVT OldVT = N->getValueType(0);
825 MVT NewVT = TLI.getTypeToTransformTo(OldVT);
826 assert(OldVT.getSizeInBits() == 2 * NewVT.getSizeInBits() &&
827 "Do not know how to handle this expansion!");
829 SDOperand NewVec = DAG.getNode(ISD::BIT_CONVERT,
830 MVT::getVectorVT(NewVT, 2*OldElts),
833 // Extract the elements at 2 * Idx and 2 * Idx + 1 from the new vector.
834 SDOperand Idx = N->getOperand(1);
836 // Make sure the type of Idx is big enough to hold the new values.
837 if (Idx.getValueType().bitsLT(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 NVT = InL.getValueType();
860 unsigned VTBits = N->getValueType(0).getSizeInBits();
861 unsigned NVTBits = NVT.getSizeInBits();
862 MVT 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 NVT = TLI.getTypeToTransformTo(N->getValueType(0));
936 MVT ShTy = Amt.getValueType();
937 unsigned ShBits = ShTy.getSizeInBits();
938 unsigned NVTBits = NVT.getSizeInBits();
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 (N->getValueType(0).isVector()) {
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 OVT = N->getOperand(0).getValueType();
1087 MVT NVT = MVT::getVectorVT(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,
1107 // We know the destination is legal, but that the input needs to be expanded.
1108 MVT 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,
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 (DestTy.bitsGT(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 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 VT = N->getOperand(1).getValueType();
1347 MVT 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(!(NVT.getSizeInBits() & 7) && "Expanded type not byte sized!");
1357 if (!N->isTruncatingStore()) {
1358 unsigned IncrementSize = 0;
1359 GetExpandedOp(N->getValue(), Lo, Hi);
1360 IncrementSize = Hi.getValueType().getSizeInBits()/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 (N->getMemoryVT().bitsLE(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 N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
1387 MVT NEVT = MVT::getIntegerVT(ExcessBits);
1389 // Increment the pointer to the other half.
1390 unsigned IncrementSize = NVT.getSizeInBits()/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 EVT = N->getMemoryVT();
1403 unsigned EBytes = EVT.getStoreSizeInBits()/8;
1404 unsigned IncrementSize = NVT.getSizeInBits()/8;
1405 unsigned ExcessBits = (EBytes - IncrementSize)*8;
1406 MVT HiVT = MVT::getIntegerVT(EVT.getSizeInBits() - ExcessBits);
1408 if (ExcessBits < NVT.getSizeInBits()) {
1409 // Transfer high bits from the top of Lo to the bottom of Hi.
1410 Hi = DAG.getNode(ISD::SHL, NVT, Hi,
1411 DAG.getConstant(NVT.getSizeInBits() - ExcessBits,
1412 TLI.getShiftAmountTy()));
1413 Hi = DAG.getNode(ISD::OR, NVT, Hi,
1414 DAG.getNode(ISD::SRL, NVT, Lo,
1415 DAG.getConstant(ExcessBits,
1416 TLI.getShiftAmountTy())));
1419 // Store both the high bits and maybe some of the low bits.
1420 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1421 SVOffset, HiVT, isVolatile, Alignment);
1423 // Increment the pointer to the other half.
1424 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1425 DAG.getIntPtrConstant(IncrementSize));
1426 // Store the lowest ExcessBits bits in the second half.
1427 Lo = DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(),
1428 SVOffset+IncrementSize,
1429 MVT::getIntegerVT(ExcessBits),
1430 isVolatile, MinAlign(Alignment, IncrementSize));
1431 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1435 SDOperand DAGTypeLegalizer::ExpandOperand_BUILD_VECTOR(SDNode *N) {
1436 // The vector type is legal but the element type needs expansion.
1437 MVT VecVT = N->getValueType(0);
1438 unsigned NumElts = VecVT.getVectorNumElements();
1439 MVT OldVT = N->getOperand(0).getValueType();
1440 MVT NewVT = TLI.getTypeToTransformTo(OldVT);
1442 assert(OldVT.getSizeInBits() == 2 * NewVT.getSizeInBits() &&
1443 "Do not know how to expand this operand!");
1445 // Build a vector of twice the length out of the expanded elements.
1446 // For example <2 x i64> -> <4 x i32>.
1447 std::vector<SDOperand> NewElts;
1448 NewElts.reserve(NumElts*2);
1450 for (unsigned i = 0; i < NumElts; ++i) {
1452 GetExpandedOp(N->getOperand(i), Lo, Hi);
1453 if (TLI.isBigEndian())
1455 NewElts.push_back(Lo);
1456 NewElts.push_back(Hi);
1459 SDOperand NewVec = DAG.getNode(ISD::BUILD_VECTOR,
1460 MVT::getVectorVT(NewVT, NewElts.size()),
1461 &NewElts[0], NewElts.size());
1463 // Convert the new vector to the old vector type.
1464 return DAG.getNode(ISD::BIT_CONVERT, VecVT, NewVec);