1 //===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Chris Lattner and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SelectionDAG::LegalizeTypes method. It transforms
11 // an arbitrary well-formed SelectionDAG to only consist of legal types. This
12 // is common code shared among the LegalizeTypes*.cpp files.
14 //===----------------------------------------------------------------------===//
16 #include "LegalizeTypes.h"
17 #include "llvm/Constants.h"
18 #include "llvm/DerivedTypes.h"
19 #include "llvm/Support/MathExtras.h"
22 /// run - This is the main entry point for the type legalizer. This does a
23 /// top-down traversal of the dag, legalizing types as it goes.
24 void DAGTypeLegalizer::run() {
25 // Create a dummy node (which is not added to allnodes), that adds a reference
26 // to the root node, preventing it from being deleted, and tracking any
27 // changes of the root.
28 HandleSDNode Dummy(DAG.getRoot());
30 // The root of the dag may dangle to deleted nodes until the type legalizer is
31 // done. Set it to null to avoid confusion.
32 DAG.setRoot(SDOperand());
34 // Walk all nodes in the graph, assigning them a NodeID of 'ReadyToProcess'
35 // (and remembering them) if they are leaves and assigning 'NewNode' if
37 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
38 E = DAG.allnodes_end(); I != E; ++I) {
39 if (I->getNumOperands() == 0) {
40 I->setNodeId(ReadyToProcess);
41 Worklist.push_back(I);
43 I->setNodeId(NewNode);
47 // Now that we have a set of nodes to process, handle them all.
48 while (!Worklist.empty()) {
49 SDNode *N = Worklist.back();
51 assert(N->getNodeId() == ReadyToProcess &&
52 "Node should be ready if on worklist!");
54 // Scan the values produced by the node, checking to see if any result
57 unsigned NumResults = N->getNumValues();
59 MVT::ValueType ResultVT = N->getValueType(i);
60 LegalizeAction Action = getTypeAction(ResultVT);
61 if (Action == Promote) {
64 } else if (Action == Expand) {
65 // Expand can mean 1) split integer in half 2) scalarize single-element
66 // vector 3) split vector in half.
67 if (!MVT::isVector(ResultVT))
69 else if (MVT::getVectorNumElements(ResultVT) == 1)
70 ScalarizeResult(N, i); // Scalarize the single-element vector.
71 else // Split the vector in half.
72 assert(0 && "Vector splitting not implemented");
75 assert(Action == Legal && "Unknown action!");
77 } while (++i < NumResults);
79 // Scan the operand list for the node, handling any nodes with operands that
82 unsigned NumOperands = N->getNumOperands();
83 bool NeedsRevisit = false;
84 for (i = 0; i != NumOperands; ++i) {
85 MVT::ValueType OpVT = N->getOperand(i).getValueType();
86 LegalizeAction Action = getTypeAction(OpVT);
87 if (Action == Promote) {
88 NeedsRevisit = PromoteOperand(N, i);
90 } else if (Action == Expand) {
91 // Expand can mean 1) split integer in half 2) scalarize single-element
92 // vector 3) split vector in half.
93 if (!MVT::isVector(OpVT)) {
94 NeedsRevisit = ExpandOperand(N, i);
95 } else if (MVT::getVectorNumElements(OpVT) == 1) {
96 // Scalarize the single-element vector.
97 NeedsRevisit = ScalarizeOperand(N, i);
99 // Split the vector in half.
100 assert(0 && "Vector splitting not implemented");
104 assert(Action == Legal && "Unknown action!");
108 // If the node needs revisiting, don't add all users to the worklist etc.
112 if (i == NumOperands)
113 DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n");
117 // If we reach here, the node was processed, potentially creating new nodes.
118 // Mark it as processed and add its users to the worklist as appropriate.
119 N->setNodeId(Processed);
121 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
124 int NodeID = User->getNodeId();
125 assert(NodeID != ReadyToProcess && NodeID != Processed &&
126 "Invalid node id for user of unprocessed node!");
128 // This node has two options: it can either be a new node or its Node ID
129 // may be a count of the number of operands it has that are not ready.
131 User->setNodeId(NodeID-1);
133 // If this was the last use it was waiting on, add it to the ready list.
134 if (NodeID-1 == ReadyToProcess)
135 Worklist.push_back(User);
139 // Otherwise, this node is new: this is the first operand of it that
140 // became ready. Its new NodeID is the number of operands it has minus 1
141 // (as this node is now processed).
142 assert(NodeID == NewNode && "Unknown node ID!");
143 User->setNodeId(User->getNumOperands()-1);
145 // If the node only has a single operand, it is now ready.
146 if (User->getNumOperands() == 1)
147 Worklist.push_back(User);
151 // If the root changed (e.g. it was a dead load, update the root).
152 DAG.setRoot(Dummy.getValue());
156 // Remove dead nodes. This is important to do for cleanliness but also before
157 // the checking loop below. Implicit folding by the DAG.getNode operators can
158 // cause unreachable nodes to be around with their flags set to new.
159 DAG.RemoveDeadNodes();
161 // In a debug build, scan all the nodes to make sure we found them all. This
162 // ensures that there are no cycles and that everything got processed.
164 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
165 E = DAG.allnodes_end(); I != E; ++I) {
166 if (I->getNodeId() == Processed)
168 cerr << "Unprocessed node: ";
169 I->dump(&DAG); cerr << "\n";
171 if (I->getNodeId() == NewNode)
172 cerr << "New node not 'noticed'?\n";
173 else if (I->getNodeId() > 0)
174 cerr << "Operand not processed?\n";
175 else if (I->getNodeId() == ReadyToProcess)
176 cerr << "Not added to worklist?\n";
182 /// MarkNewNodes - The specified node is the root of a subtree of potentially
183 /// new nodes. Add the correct NodeId to mark it.
184 void DAGTypeLegalizer::MarkNewNodes(SDNode *N) {
185 // If this was an existing node that is already done, we're done.
186 if (N->getNodeId() != NewNode)
189 // Okay, we know that this node is new. Recursively walk all of its operands
190 // to see if they are new also. The depth of this walk is bounded by the size
191 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry
192 // about revisiting of nodes.
194 // As we walk the operands, keep track of the number of nodes that are
195 // processed. If non-zero, this will become the new nodeid of this node.
196 unsigned NumProcessed = 0;
197 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
198 int OpId = N->getOperand(i).Val->getNodeId();
200 MarkNewNodes(N->getOperand(i).Val);
201 else if (OpId == Processed)
205 N->setNodeId(N->getNumOperands()-NumProcessed);
206 if (N->getNodeId() == ReadyToProcess)
207 Worklist.push_back(N);
210 /// ReplaceValueWith - The specified value was legalized to the specified other
211 /// value. If they are different, update the DAG and NodeIDs replacing any uses
212 /// of From to use To instead.
213 void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) {
214 if (From == To) return;
216 // If expansion produced new nodes, make sure they are properly marked.
217 if (To.Val->getNodeId() == NewNode)
218 MarkNewNodes(To.Val);
220 // Anything that used the old node should now use the new one. Note that this
221 // can potentially cause recursive merging.
222 DAG.ReplaceAllUsesOfValueWith(From, To);
224 // The old node may still be present in ExpandedNodes or PromotedNodes.
225 // Inform them about the replacement.
226 ReplacedNodes[From] = To;
228 // Since we just made an unstructured update to the DAG, which could wreak
229 // general havoc on anything that once used From and now uses To, walk all
230 // users of the result, updating their flags.
231 for (SDNode::use_iterator I = To.Val->use_begin(), E = To.Val->use_end();
234 // If the node isn't already processed or in the worklist, mark it as new,
235 // then use MarkNewNodes to recompute its ID.
236 int NodeId = User->getNodeId();
237 if (NodeId != ReadyToProcess && NodeId != Processed) {
238 User->setNodeId(NewNode);
244 /// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to'
245 /// node's results. The from and to node must define identical result types.
246 void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) {
247 if (From == To) return;
248 assert(From->getNumValues() == To->getNumValues() &&
249 "Node results don't match");
251 // If expansion produced new nodes, make sure they are properly marked.
252 if (To->getNodeId() == NewNode)
255 // Anything that used the old node should now use the new one. Note that this
256 // can potentially cause recursive merging.
257 DAG.ReplaceAllUsesWith(From, To);
259 // The old node may still be present in ExpandedNodes or PromotedNodes.
260 // Inform them about the replacement.
261 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) {
262 assert(From->getValueType(i) == To->getValueType(i) &&
263 "Node results don't match");
264 ReplacedNodes[SDOperand(From, i)] = SDOperand(To, i);
267 // Since we just made an unstructured update to the DAG, which could wreak
268 // general havoc on anything that once used From and now uses To, walk all
269 // users of the result, updating their flags.
270 for (SDNode::use_iterator I = To->use_begin(), E = To->use_end();I != E; ++I){
272 // If the node isn't already processed or in the worklist, mark it as new,
273 // then use MarkNewNodes to recompute its ID.
274 int NodeId = User->getNodeId();
275 if (NodeId != ReadyToProcess && NodeId != Processed) {
276 User->setNodeId(NewNode);
283 /// RemapNode - If the specified value was already legalized to another value,
284 /// replace it by that value.
285 void DAGTypeLegalizer::RemapNode(SDOperand &N) {
286 DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.find(N);
287 if (I != ReplacedNodes.end()) {
288 // Use path compression to speed up future lookups if values get multiply
289 // replaced with other values.
290 RemapNode(I->second);
295 void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) {
296 if (Result.Val->getNodeId() == NewNode)
297 MarkNewNodes(Result.Val);
299 SDOperand &OpEntry = PromotedNodes[Op];
300 assert(OpEntry.Val == 0 && "Node is already promoted!");
304 void DAGTypeLegalizer::SetScalarizedOp(SDOperand Op, SDOperand Result) {
305 if (Result.Val->getNodeId() == NewNode)
306 MarkNewNodes(Result.Val);
308 SDOperand &OpEntry = ScalarizedNodes[Op];
309 assert(OpEntry.Val == 0 && "Node is already scalarized!");
314 void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo,
316 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op];
317 RemapNode(Entry.first);
318 RemapNode(Entry.second);
319 assert(Entry.first.Val && "Operand isn't expanded");
324 void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo,
326 // Remember that this is the result of the node.
327 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op];
328 assert(Entry.first.Val == 0 && "Node already expanded");
332 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
333 if (Lo.Val->getNodeId() == NewNode)
334 MarkNewNodes(Lo.Val);
335 if (Hi.Val->getNodeId() == NewNode)
336 MarkNewNodes(Hi.Val);
339 SDOperand DAGTypeLegalizer::CreateStackStoreLoad(SDOperand Op,
340 MVT::ValueType DestVT) {
341 // Create the stack frame object.
342 SDOperand FIPtr = DAG.CreateStackTemporary(DestVT);
344 // Emit a store to the stack slot.
345 SDOperand Store = DAG.getStore(DAG.getEntryNode(), Op, FIPtr, NULL, 0);
346 // Result is a load from the stack slot.
347 return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0);
350 /// HandleMemIntrinsic - This handles memcpy/memset/memmove with invalid
351 /// operands. This promotes or expands the operands as required.
352 SDOperand DAGTypeLegalizer::HandleMemIntrinsic(SDNode *N) {
353 // The chain and pointer [operands #0 and #1] are always valid types.
354 SDOperand Chain = N->getOperand(0);
355 SDOperand Ptr = N->getOperand(1);
356 SDOperand Op2 = N->getOperand(2);
358 // Op #2 is either a value (memset) or a pointer. Promote it if required.
359 switch (getTypeAction(Op2.getValueType())) {
360 default: assert(0 && "Unknown action for pointer/value operand");
362 case Promote: Op2 = GetPromotedOp(Op2); break;
365 // The length could have any action required.
366 SDOperand Length = N->getOperand(3);
367 switch (getTypeAction(Length.getValueType())) {
368 default: assert(0 && "Unknown action for memop operand");
370 case Promote: Length = GetPromotedZExtOp(Length); break;
372 SDOperand Dummy; // discard the high part.
373 GetExpandedOp(Length, Length, Dummy);
377 SDOperand Align = N->getOperand(4);
378 switch (getTypeAction(Align.getValueType())) {
379 default: assert(0 && "Unknown action for memop operand");
381 case Promote: Align = GetPromotedZExtOp(Align); break;
384 SDOperand AlwaysInline = N->getOperand(5);
385 switch (getTypeAction(AlwaysInline.getValueType())) {
386 default: assert(0 && "Unknown action for memop operand");
388 case Promote: AlwaysInline = GetPromotedZExtOp(AlwaysInline); break;
391 SDOperand Ops[] = { Chain, Ptr, Op2, Length, Align, AlwaysInline };
392 return DAG.UpdateNodeOperands(SDOperand(N, 0), Ops, 6);
395 /// SplitOp - Return the lower and upper halves of Op's bits in a value type
396 /// half the size of Op's.
397 void DAGTypeLegalizer::SplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) {
398 unsigned NVTBits = MVT::getSizeInBits(Op.getValueType())/2;
399 assert(MVT::getSizeInBits(Op.getValueType()) == 2*NVTBits &&
400 "Cannot split odd sized integer type");
401 MVT::ValueType NVT = MVT::getIntegerType(NVTBits);
402 Lo = DAG.getNode(ISD::TRUNCATE, NVT, Op);
403 Hi = DAG.getNode(ISD::SRL, Op.getValueType(), Op,
404 DAG.getConstant(NVTBits, TLI.getShiftAmountTy()));
405 Hi = DAG.getNode(ISD::TRUNCATE, NVT, Hi);
409 //===----------------------------------------------------------------------===//
411 //===----------------------------------------------------------------------===//
413 /// ExpandResult - This method is called when the specified result of the
414 /// specified node is found to need expansion. At this point, the node may also
415 /// have invalid operands or may have other results that need promotion, we just
416 /// know that (at least) one result needs expansion.
417 void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) {
418 DEBUG(cerr << "Expand node result: "; N->dump(&DAG); cerr << "\n");
420 Lo = Hi = SDOperand();
422 // See if the target wants to custom expand this node.
423 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
424 TargetLowering::Custom) {
425 // If the target wants to, allow it to lower this itself.
426 if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) {
427 // Everything that once used N now uses P. We are guaranteed that the
428 // result value types of N and the result value types of P match.
429 ReplaceNodeWith(N, P);
434 switch (N->getOpcode()) {
437 cerr << "ExpandResult #" << ResNo << ": ";
438 N->dump(&DAG); cerr << "\n";
440 assert(0 && "Do not know how to expand the result of this operator!");
443 case ISD::UNDEF: ExpandResult_UNDEF(N, Lo, Hi); break;
444 case ISD::Constant: ExpandResult_Constant(N, Lo, Hi); break;
445 case ISD::BUILD_PAIR: ExpandResult_BUILD_PAIR(N, Lo, Hi); break;
446 case ISD::MERGE_VALUES: ExpandResult_MERGE_VALUES(N, Lo, Hi); break;
447 case ISD::ANY_EXTEND: ExpandResult_ANY_EXTEND(N, Lo, Hi); break;
448 case ISD::ZERO_EXTEND: ExpandResult_ZERO_EXTEND(N, Lo, Hi); break;
449 case ISD::SIGN_EXTEND: ExpandResult_SIGN_EXTEND(N, Lo, Hi); break;
450 case ISD::BIT_CONVERT: ExpandResult_BIT_CONVERT(N, Lo, Hi); break;
451 case ISD::SIGN_EXTEND_INREG: ExpandResult_SIGN_EXTEND_INREG(N, Lo, Hi); break;
452 case ISD::LOAD: ExpandResult_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
456 case ISD::XOR: ExpandResult_Logical(N, Lo, Hi); break;
457 case ISD::BSWAP: ExpandResult_BSWAP(N, Lo, Hi); break;
459 case ISD::SUB: ExpandResult_ADDSUB(N, Lo, Hi); break;
461 case ISD::SUBC: ExpandResult_ADDSUBC(N, Lo, Hi); break;
463 case ISD::SUBE: ExpandResult_ADDSUBE(N, Lo, Hi); break;
464 case ISD::SELECT: ExpandResult_SELECT(N, Lo, Hi); break;
465 case ISD::SELECT_CC: ExpandResult_SELECT_CC(N, Lo, Hi); break;
466 case ISD::MUL: ExpandResult_MUL(N, Lo, Hi); break;
469 case ISD::SRL: ExpandResult_Shift(N, Lo, Hi); break;
472 // If Lo/Hi is null, the sub-method took care of registering results etc.
474 SetExpandedOp(SDOperand(N, ResNo), Lo, Hi);
477 void DAGTypeLegalizer::ExpandResult_UNDEF(SDNode *N,
478 SDOperand &Lo, SDOperand &Hi) {
479 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
480 Lo = Hi = DAG.getNode(ISD::UNDEF, NVT);
483 void DAGTypeLegalizer::ExpandResult_Constant(SDNode *N,
484 SDOperand &Lo, SDOperand &Hi) {
485 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
486 uint64_t Cst = cast<ConstantSDNode>(N)->getValue();
487 Lo = DAG.getConstant(Cst, NVT);
488 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
491 void DAGTypeLegalizer::ExpandResult_BUILD_PAIR(SDNode *N,
492 SDOperand &Lo, SDOperand &Hi) {
493 // Return the operands.
494 Lo = N->getOperand(0);
495 Hi = N->getOperand(1);
498 void DAGTypeLegalizer::ExpandResult_MERGE_VALUES(SDNode *N,
499 SDOperand &Lo, SDOperand &Hi) {
500 // A MERGE_VALUES node can produce any number of values. We know that the
501 // first illegal one needs to be expanded into Lo/Hi.
504 // The string of legal results gets turns into the input operands, which have
506 for (i = 0; isTypeLegal(N->getValueType(i)); ++i)
507 ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
509 // The first illegal result must be the one that needs to be expanded.
510 GetExpandedOp(N->getOperand(i), Lo, Hi);
512 // Legalize the rest of the results into the input operands whether they are
514 unsigned e = N->getNumValues();
515 for (++i; i != e; ++i)
516 ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
519 void DAGTypeLegalizer::ExpandResult_ANY_EXTEND(SDNode *N,
520 SDOperand &Lo, SDOperand &Hi) {
521 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
522 SDOperand Op = N->getOperand(0);
523 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
524 // The low part is any extension of the input (which degenerates to a copy).
525 Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Op);
526 Hi = DAG.getNode(ISD::UNDEF, NVT); // The high part is undefined.
528 // For example, extension of an i48 to an i64. The operand type necessarily
529 // promotes to the result type, so will end up being expanded too.
530 assert(getTypeAction(Op.getValueType()) == Promote &&
531 "Don't know how to expand this result!");
532 SDOperand Res = GetPromotedOp(Op);
533 assert(Res.getValueType() == N->getValueType(0) &&
534 "Operand over promoted?");
535 // Split the promoted operand. This will simplify when it is expanded.
536 SplitOp(Res, Lo, Hi);
540 void DAGTypeLegalizer::ExpandResult_ZERO_EXTEND(SDNode *N,
541 SDOperand &Lo, SDOperand &Hi) {
542 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
543 SDOperand Op = N->getOperand(0);
544 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
545 // The low part is zero extension of the input (which degenerates to a copy).
546 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, N->getOperand(0));
547 Hi = DAG.getConstant(0, NVT); // The high part is just a zero.
549 // For example, extension of an i48 to an i64. The operand type necessarily
550 // promotes to the result type, so will end up being expanded too.
551 assert(getTypeAction(Op.getValueType()) == Promote &&
552 "Don't know how to expand this result!");
553 SDOperand Res = GetPromotedOp(Op);
554 assert(Res.getValueType() == N->getValueType(0) &&
555 "Operand over promoted?");
556 // Split the promoted operand. This will simplify when it is expanded.
557 SplitOp(Res, Lo, Hi);
558 unsigned ExcessBits =
559 MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT);
560 Hi = DAG.getZeroExtendInReg(Hi, MVT::getIntegerType(ExcessBits));
564 void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N,
565 SDOperand &Lo, SDOperand &Hi) {
566 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
567 SDOperand Op = N->getOperand(0);
568 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) {
569 // The low part is sign extension of the input (which degenerates to a copy).
570 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, N->getOperand(0));
571 // The high part is obtained by SRA'ing all but one of the bits of low part.
572 unsigned LoSize = MVT::getSizeInBits(NVT);
573 Hi = DAG.getNode(ISD::SRA, NVT, Lo,
574 DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
576 // For example, extension of an i48 to an i64. The operand type necessarily
577 // promotes to the result type, so will end up being expanded too.
578 assert(getTypeAction(Op.getValueType()) == Promote &&
579 "Don't know how to expand this result!");
580 SDOperand Res = GetPromotedOp(Op);
581 assert(Res.getValueType() == N->getValueType(0) &&
582 "Operand over promoted?");
583 // Split the promoted operand. This will simplify when it is expanded.
584 SplitOp(Res, Lo, Hi);
585 unsigned ExcessBits =
586 MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT);
587 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
588 DAG.getValueType(MVT::getIntegerType(ExcessBits)));
592 void DAGTypeLegalizer::ExpandResult_BIT_CONVERT(SDNode *N,
593 SDOperand &Lo, SDOperand &Hi) {
594 // Lower the bit-convert to a store/load from the stack, then expand the load.
595 SDOperand Op = CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
596 ExpandResult_LOAD(cast<LoadSDNode>(Op.Val), Lo, Hi);
599 void DAGTypeLegalizer::
600 ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
601 GetExpandedOp(N->getOperand(0), Lo, Hi);
602 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
604 if (MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(Lo.getValueType())) {
605 // sext_inreg the low part if needed.
606 Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, Lo.getValueType(), Lo,
609 // The high part gets the sign extension from the lo-part. This handles
610 // things like sextinreg V:i64 from i8.
611 Hi = DAG.getNode(ISD::SRA, Hi.getValueType(), Lo,
612 DAG.getConstant(MVT::getSizeInBits(Hi.getValueType())-1,
613 TLI.getShiftAmountTy()));
615 // For example, extension of an i48 to an i64. Leave the low part alone,
616 // sext_inreg the high part.
617 unsigned ExcessBits =
618 MVT::getSizeInBits(EVT) - MVT::getSizeInBits(Lo.getValueType());
619 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi,
620 DAG.getValueType(MVT::getIntegerType(ExcessBits)));
624 void DAGTypeLegalizer::ExpandResult_LOAD(LoadSDNode *N,
625 SDOperand &Lo, SDOperand &Hi) {
626 MVT::ValueType VT = N->getValueType(0);
627 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
628 SDOperand Ch = N->getChain(); // Legalize the chain.
629 SDOperand Ptr = N->getBasePtr(); // Legalize the pointer.
630 ISD::LoadExtType ExtType = N->getExtensionType();
631 int SVOffset = N->getSrcValueOffset();
632 unsigned Alignment = N->getAlignment();
633 bool isVolatile = N->isVolatile();
635 assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!");
637 if (ExtType == ISD::NON_EXTLOAD) {
638 Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
639 isVolatile, Alignment);
640 // Increment the pointer to the other half.
641 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
642 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
643 getIntPtrConstant(IncrementSize));
644 Hi = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
645 isVolatile, MinAlign(Alignment, IncrementSize));
647 // Build a factor node to remember that this load is independent of the
649 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
652 // Handle endianness of the load.
653 if (!TLI.isLittleEndian())
655 } else if (MVT::getSizeInBits(N->getLoadedVT()) <= MVT::getSizeInBits(NVT)) {
656 MVT::ValueType EVT = N->getLoadedVT();
658 Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset, EVT,
659 isVolatile, Alignment);
661 // Remember the chain.
664 if (ExtType == ISD::SEXTLOAD) {
665 // The high part is obtained by SRA'ing all but one of the bits of the
667 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
668 Hi = DAG.getNode(ISD::SRA, NVT, Lo,
669 DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
670 } else if (ExtType == ISD::ZEXTLOAD) {
671 // The high part is just a zero.
672 Hi = DAG.getConstant(0, NVT);
674 assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
675 // The high part is undefined.
676 Hi = DAG.getNode(ISD::UNDEF, NVT);
678 } else if (TLI.isLittleEndian()) {
679 // Little-endian - low bits are at low addresses.
680 Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
681 isVolatile, Alignment);
683 unsigned ExcessBits =
684 MVT::getSizeInBits(N->getLoadedVT()) - MVT::getSizeInBits(NVT);
685 MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits);
687 // Increment the pointer to the other half.
688 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
689 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
690 getIntPtrConstant(IncrementSize));
691 Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(),
692 SVOffset+IncrementSize, NEVT,
693 isVolatile, MinAlign(Alignment, IncrementSize));
695 // Build a factor node to remember that this load is independent of the
697 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
700 // Big-endian - high bits are at low addresses. Favor aligned loads at
701 // the cost of some bit-fiddling.
702 MVT::ValueType EVT = N->getLoadedVT();
703 unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8;
704 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
705 unsigned ExcessBits = (EBytes - IncrementSize)*8;
707 // Load both the high bits and maybe some of the low bits.
708 Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
709 MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits),
710 isVolatile, Alignment);
712 // Increment the pointer to the other half.
713 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
714 getIntPtrConstant(IncrementSize));
715 // Load the rest of the low bits.
716 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Ch, Ptr, N->getSrcValue(),
717 SVOffset+IncrementSize, MVT::getIntegerType(ExcessBits),
718 isVolatile, MinAlign(Alignment, IncrementSize));
720 // Build a factor node to remember that this load is independent of the
722 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
725 if (ExcessBits < MVT::getSizeInBits(NVT)) {
726 // Transfer low bits from the bottom of Hi to the top of Lo.
727 Lo = DAG.getNode(ISD::OR, NVT, Lo,
728 DAG.getNode(ISD::SHL, NVT, Hi,
729 DAG.getConstant(ExcessBits,
730 TLI.getShiftAmountTy())));
731 // Move high bits to the right position in Hi.
732 Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, NVT, Hi,
733 DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits,
734 TLI.getShiftAmountTy()));
738 // Legalized the chain result - switch anything that used the old chain to
740 ReplaceValueWith(SDOperand(N, 1), Ch);
743 void DAGTypeLegalizer::ExpandResult_Logical(SDNode *N,
744 SDOperand &Lo, SDOperand &Hi) {
745 SDOperand LL, LH, RL, RH;
746 GetExpandedOp(N->getOperand(0), LL, LH);
747 GetExpandedOp(N->getOperand(1), RL, RH);
748 Lo = DAG.getNode(N->getOpcode(), LL.getValueType(), LL, RL);
749 Hi = DAG.getNode(N->getOpcode(), LL.getValueType(), LH, RH);
752 void DAGTypeLegalizer::ExpandResult_BSWAP(SDNode *N,
753 SDOperand &Lo, SDOperand &Hi) {
754 GetExpandedOp(N->getOperand(0), Hi, Lo); // Note swapped operands.
755 Lo = DAG.getNode(ISD::BSWAP, Lo.getValueType(), Lo);
756 Hi = DAG.getNode(ISD::BSWAP, Hi.getValueType(), Hi);
759 void DAGTypeLegalizer::ExpandResult_SELECT(SDNode *N,
760 SDOperand &Lo, SDOperand &Hi) {
761 SDOperand LL, LH, RL, RH;
762 GetExpandedOp(N->getOperand(1), LL, LH);
763 GetExpandedOp(N->getOperand(2), RL, RH);
764 Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LL, RL);
766 assert(N->getOperand(0).getValueType() != MVT::f32 &&
767 "FIXME: softfp shouldn't use expand!");
768 Hi = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LH, RH);
771 void DAGTypeLegalizer::ExpandResult_SELECT_CC(SDNode *N,
772 SDOperand &Lo, SDOperand &Hi) {
773 SDOperand LL, LH, RL, RH;
774 GetExpandedOp(N->getOperand(2), LL, LH);
775 GetExpandedOp(N->getOperand(3), RL, RH);
776 Lo = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
777 N->getOperand(1), LL, RL, N->getOperand(4));
779 assert(N->getOperand(0).getValueType() != MVT::f32 &&
780 "FIXME: softfp shouldn't use expand!");
781 Hi = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0),
782 N->getOperand(1), LH, RH, N->getOperand(4));
785 void DAGTypeLegalizer::ExpandResult_ADDSUB(SDNode *N,
786 SDOperand &Lo, SDOperand &Hi) {
787 // Expand the subcomponents.
788 SDOperand LHSL, LHSH, RHSL, RHSH;
789 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
790 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
791 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
792 SDOperand LoOps[2] = { LHSL, RHSL };
793 SDOperand HiOps[3] = { LHSH, RHSH };
795 if (N->getOpcode() == ISD::ADD) {
796 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
797 HiOps[2] = Lo.getValue(1);
798 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
800 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
801 HiOps[2] = Lo.getValue(1);
802 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
806 void DAGTypeLegalizer::ExpandResult_ADDSUBC(SDNode *N,
807 SDOperand &Lo, SDOperand &Hi) {
808 // Expand the subcomponents.
809 SDOperand LHSL, LHSH, RHSL, RHSH;
810 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
811 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
812 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
813 SDOperand LoOps[2] = { LHSL, RHSL };
814 SDOperand HiOps[3] = { LHSH, RHSH };
816 if (N->getOpcode() == ISD::ADDC) {
817 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
818 HiOps[2] = Lo.getValue(1);
819 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
821 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
822 HiOps[2] = Lo.getValue(1);
823 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
826 // Legalized the flag result - switch anything that used the old flag to
828 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
831 void DAGTypeLegalizer::ExpandResult_ADDSUBE(SDNode *N,
832 SDOperand &Lo, SDOperand &Hi) {
833 // Expand the subcomponents.
834 SDOperand LHSL, LHSH, RHSL, RHSH;
835 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
836 GetExpandedOp(N->getOperand(1), RHSL, RHSH);
837 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
838 SDOperand LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
839 SDOperand HiOps[3] = { LHSH, RHSH };
841 Lo = DAG.getNode(N->getOpcode(), VTList, LoOps, 3);
842 HiOps[2] = Lo.getValue(1);
843 Hi = DAG.getNode(N->getOpcode(), VTList, HiOps, 3);
845 // Legalized the flag result - switch anything that used the old flag to
847 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1));
850 void DAGTypeLegalizer::ExpandResult_MUL(SDNode *N,
851 SDOperand &Lo, SDOperand &Hi) {
852 MVT::ValueType VT = N->getValueType(0);
853 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
855 bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT);
856 bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT);
857 bool HasSMUL_LOHI = TLI.isOperationLegal(ISD::SMUL_LOHI, NVT);
858 bool HasUMUL_LOHI = TLI.isOperationLegal(ISD::UMUL_LOHI, NVT);
859 if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
860 SDOperand LL, LH, RL, RH;
861 GetExpandedOp(N->getOperand(0), LL, LH);
862 GetExpandedOp(N->getOperand(1), RL, RH);
863 unsigned BitSize = MVT::getSizeInBits(NVT);
864 unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
865 unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
867 // FIXME: generalize this to handle other bit sizes
868 if (LHSSB == 32 && RHSSB == 32 &&
869 DAG.MaskedValueIsZero(N->getOperand(0), 0xFFFFFFFF00000000ULL) &&
870 DAG.MaskedValueIsZero(N->getOperand(1), 0xFFFFFFFF00000000ULL)) {
871 // The inputs are both zero-extended.
873 // We can emit a umul_lohi.
874 Lo = DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
875 Hi = SDOperand(Lo.Val, 1);
879 // We can emit a mulhu+mul.
880 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
881 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
885 if (LHSSB > BitSize && RHSSB > BitSize) {
886 // The input values are both sign-extended.
888 // We can emit a smul_lohi.
889 Lo = DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL);
890 Hi = SDOperand(Lo.Val, 1);
894 // We can emit a mulhs+mul.
895 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
896 Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
901 // Lo,Hi = umul LHS, RHS.
902 SDOperand UMulLOHI = DAG.getNode(ISD::UMUL_LOHI,
903 DAG.getVTList(NVT, NVT), LL, RL);
905 Hi = UMulLOHI.getValue(1);
906 RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
907 LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
908 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
909 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
916 // If nothing else, we can make a libcall.
917 Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::MUL_I64), N,
918 false/*sign irrelevant*/, Hi);
923 void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N,
924 SDOperand &Lo, SDOperand &Hi) {
925 MVT::ValueType VT = N->getValueType(0);
927 // If we can emit an efficient shift operation, do so now. Check to see if
928 // the RHS is a constant.
929 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
930 return ExpandShiftByConstant(N, CN->getValue(), Lo, Hi);
932 // If we can determine that the high bit of the shift is zero or one, even if
933 // the low bits are variable, emit this shift in an optimized form.
934 if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
937 // If this target supports shift_PARTS, use it. First, map to the _PARTS opc.
939 if (N->getOpcode() == ISD::SHL)
940 PartsOpc = ISD::SHL_PARTS;
941 else if (N->getOpcode() == ISD::SRL)
942 PartsOpc = ISD::SRL_PARTS;
944 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
945 PartsOpc = ISD::SRA_PARTS;
948 // Next check to see if the target supports this SHL_PARTS operation or if it
949 // will custom expand it.
950 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
951 TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
952 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
953 Action == TargetLowering::Custom) {
954 // Expand the subcomponents.
955 SDOperand LHSL, LHSH;
956 GetExpandedOp(N->getOperand(0), LHSL, LHSH);
958 SDOperand Ops[] = { LHSL, LHSH, N->getOperand(1) };
959 MVT::ValueType VT = LHSL.getValueType();
960 Lo = DAG.getNode(PartsOpc, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3);
967 // Otherwise, emit a libcall.
968 unsigned RuntimeCode = ; // SRL -> SRL_I64 etc.
970 Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::SRL_I64), N,
971 false/*lshr is unsigned*/, Hi);
976 /// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
977 /// and the shift amount is a constant 'Amt'. Expand the operation.
978 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt,
979 SDOperand &Lo, SDOperand &Hi) {
980 // Expand the incoming operand to be shifted, so that we have its parts
982 GetExpandedOp(N->getOperand(0), InL, InH);
984 MVT::ValueType NVT = InL.getValueType();
985 unsigned VTBits = MVT::getSizeInBits(N->getValueType(0));
986 unsigned NVTBits = MVT::getSizeInBits(NVT);
987 MVT::ValueType ShTy = N->getOperand(1).getValueType();
989 if (N->getOpcode() == ISD::SHL) {
991 Lo = Hi = DAG.getConstant(0, NVT);
992 } else if (Amt > NVTBits) {
993 Lo = DAG.getConstant(0, NVT);
994 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy));
995 } else if (Amt == NVTBits) {
996 Lo = DAG.getConstant(0, NVT);
999 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt, ShTy));
1000 Hi = DAG.getNode(ISD::OR, NVT,
1001 DAG.getNode(ISD::SHL, NVT, InH,
1002 DAG.getConstant(Amt, ShTy)),
1003 DAG.getNode(ISD::SRL, NVT, InL,
1004 DAG.getConstant(NVTBits-Amt, ShTy)));
1009 if (N->getOpcode() == ISD::SRL) {
1011 Lo = DAG.getConstant(0, NVT);
1012 Hi = DAG.getConstant(0, NVT);
1013 } else if (Amt > NVTBits) {
1014 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt-NVTBits,ShTy));
1015 Hi = DAG.getConstant(0, NVT);
1016 } else if (Amt == NVTBits) {
1018 Hi = DAG.getConstant(0, NVT);
1020 Lo = DAG.getNode(ISD::OR, NVT,
1021 DAG.getNode(ISD::SRL, NVT, InL,
1022 DAG.getConstant(Amt, ShTy)),
1023 DAG.getNode(ISD::SHL, NVT, InH,
1024 DAG.getConstant(NVTBits-Amt, ShTy)));
1025 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt, ShTy));
1030 assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
1032 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
1033 DAG.getConstant(NVTBits-1, ShTy));
1034 } else if (Amt > NVTBits) {
1035 Lo = DAG.getNode(ISD::SRA, NVT, InH,
1036 DAG.getConstant(Amt-NVTBits, ShTy));
1037 Hi = DAG.getNode(ISD::SRA, NVT, InH,
1038 DAG.getConstant(NVTBits-1, ShTy));
1039 } else if (Amt == NVTBits) {
1041 Hi = DAG.getNode(ISD::SRA, NVT, InH,
1042 DAG.getConstant(NVTBits-1, ShTy));
1044 Lo = DAG.getNode(ISD::OR, NVT,
1045 DAG.getNode(ISD::SRL, NVT, InL,
1046 DAG.getConstant(Amt, ShTy)),
1047 DAG.getNode(ISD::SHL, NVT, InH,
1048 DAG.getConstant(NVTBits-Amt, ShTy)));
1049 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Amt, ShTy));
1053 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
1054 /// this shift based on knowledge of the high bit of the shift amount. If we
1055 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
1057 bool DAGTypeLegalizer::
1058 ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi) {
1059 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0));
1060 unsigned NVTBits = MVT::getSizeInBits(NVT);
1061 assert(!(NVTBits & (NVTBits - 1)) &&
1062 "Expanded integer type size not a power of two!");
1064 uint64_t HighBitMask = NVTBits, KnownZero, KnownOne;
1065 DAG.ComputeMaskedBits(N->getOperand(1), HighBitMask, KnownZero, KnownOne);
1067 // If we don't know anything about the high bit, exit.
1068 if (((KnownZero|KnownOne) & HighBitMask) == 0)
1071 // Get the incoming operand to be shifted.
1073 GetExpandedOp(N->getOperand(0), InL, InH);
1074 SDOperand Amt = N->getOperand(1);
1076 // If we know that the high bit of the shift amount is one, then we can do
1077 // this as a couple of simple shifts.
1078 if (KnownOne & HighBitMask) {
1079 // Mask out the high bit, which we know is set.
1080 Amt = DAG.getNode(ISD::AND, Amt.getValueType(), Amt,
1081 DAG.getConstant(NVTBits-1, Amt.getValueType()));
1083 switch (N->getOpcode()) {
1084 default: assert(0 && "Unknown shift");
1086 Lo = DAG.getConstant(0, NVT); // Low part is zero.
1087 Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part.
1090 Hi = DAG.getConstant(0, NVT); // Hi part is zero.
1091 Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part.
1094 Hi = DAG.getNode(ISD::SRA, NVT, InH, // Sign extend high part.
1095 DAG.getConstant(NVTBits-1, Amt.getValueType()));
1096 Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part.
1101 // If we know that the high bit of the shift amount is zero, then we can do
1102 // this as a couple of simple shifts.
1103 assert((KnownZero & HighBitMask) && "Bad mask computation above");
1106 SDOperand Amt2 = DAG.getNode(ISD::SUB, Amt.getValueType(),
1107 DAG.getConstant(NVTBits, Amt.getValueType()),
1110 switch (N->getOpcode()) {
1111 default: assert(0 && "Unknown shift");
1112 case ISD::SHL: Op1 = ISD::SHL; Op2 = ISD::SRL; break;
1114 case ISD::SRA: Op1 = ISD::SRL; Op2 = ISD::SHL; break;
1117 Lo = DAG.getNode(N->getOpcode(), NVT, InL, Amt);
1118 Hi = DAG.getNode(ISD::OR, NVT,
1119 DAG.getNode(Op1, NVT, InH, Amt),
1120 DAG.getNode(Op2, NVT, InL, Amt2));
1124 //===----------------------------------------------------------------------===//
1125 // Result Vector Scalarization: <1 x ty> -> ty.
1126 //===----------------------------------------------------------------------===//
1129 void DAGTypeLegalizer::ScalarizeResult(SDNode *N, unsigned ResNo) {
1130 DEBUG(cerr << "Scalarize node result " << ResNo << ": "; N->dump(&DAG);
1132 SDOperand R = SDOperand();
1134 // FIXME: Custom lowering for scalarization?
1136 // See if the target wants to custom expand this node.
1137 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
1138 TargetLowering::Custom) {
1139 // If the target wants to, allow it to lower this itself.
1140 if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) {
1141 // Everything that once used N now uses P. We are guaranteed that the
1142 // result value types of N and the result value types of P match.
1143 ReplaceNodeWith(N, P);
1149 switch (N->getOpcode()) {
1152 cerr << "ScalarizeResult #" << ResNo << ": ";
1153 N->dump(&DAG); cerr << "\n";
1155 assert(0 && "Do not know how to scalarize the result of this operator!");
1158 case ISD::UNDEF: R = ScalarizeRes_UNDEF(N); break;
1159 case ISD::LOAD: R = ScalarizeRes_LOAD(cast<LoadSDNode>(N)); break;
1175 case ISD::XOR: R = ScalarizeRes_BinOp(N); break;
1180 case ISD::FCOS: R = ScalarizeRes_UnaryOp(N); break;
1181 case ISD::FPOWI: R = ScalarizeRes_FPOWI(N); break;
1182 case ISD::BUILD_VECTOR: R = N->getOperand(0); break;
1183 case ISD::INSERT_VECTOR_ELT: R = N->getOperand(1); break;
1184 case ISD::VECTOR_SHUFFLE: R = ScalarizeRes_VECTOR_SHUFFLE(N); break;
1185 case ISD::BIT_CONVERT: R = ScalarizeRes_BIT_CONVERT(N); break;
1186 case ISD::SELECT: R = ScalarizeRes_SELECT(N); break;
1189 // If R is null, the sub-method took care of registering the resul.
1191 SetScalarizedOp(SDOperand(N, ResNo), R);
1194 SDOperand DAGTypeLegalizer::ScalarizeRes_UNDEF(SDNode *N) {
1195 return DAG.getNode(ISD::UNDEF, MVT::getVectorElementType(N->getValueType(0)));
1198 SDOperand DAGTypeLegalizer::ScalarizeRes_LOAD(LoadSDNode *N) {
1199 SDOperand Result = DAG.getLoad(MVT::getVectorElementType(N->getValueType(0)),
1200 N->getChain(), N->getBasePtr(),
1201 N->getSrcValue(), N->getSrcValueOffset(),
1202 N->isVolatile(), N->getAlignment());
1204 // Legalized the chain result - switch anything that used the old chain to
1206 ReplaceValueWith(SDOperand(N, 1), Result.getValue(1));
1210 SDOperand DAGTypeLegalizer::ScalarizeRes_BinOp(SDNode *N) {
1211 SDOperand LHS = GetScalarizedOp(N->getOperand(0));
1212 SDOperand RHS = GetScalarizedOp(N->getOperand(1));
1213 return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
1216 SDOperand DAGTypeLegalizer::ScalarizeRes_UnaryOp(SDNode *N) {
1217 SDOperand Op = GetScalarizedOp(N->getOperand(0));
1218 return DAG.getNode(N->getOpcode(), Op.getValueType(), Op);
1221 SDOperand DAGTypeLegalizer::ScalarizeRes_FPOWI(SDNode *N) {
1222 SDOperand Op = GetScalarizedOp(N->getOperand(0));
1223 return DAG.getNode(ISD::FPOWI, Op.getValueType(), Op, N->getOperand(1));
1226 SDOperand DAGTypeLegalizer::ScalarizeRes_VECTOR_SHUFFLE(SDNode *N) {
1227 // Figure out if the scalar is the LHS or RHS and return it.
1228 SDOperand EltNum = N->getOperand(2).getOperand(0);
1229 unsigned Op = cast<ConstantSDNode>(EltNum)->getValue() != 0;
1230 return GetScalarizedOp(N->getOperand(Op));
1233 SDOperand DAGTypeLegalizer::ScalarizeRes_BIT_CONVERT(SDNode *N) {
1234 MVT::ValueType NewVT = MVT::getVectorElementType(N->getValueType(0));
1235 return DAG.getNode(ISD::BIT_CONVERT, NewVT, N->getOperand(0));
1238 SDOperand DAGTypeLegalizer::ScalarizeRes_SELECT(SDNode *N) {
1239 SDOperand LHS = GetScalarizedOp(N->getOperand(1));
1240 return DAG.getNode(ISD::SELECT, LHS.getValueType(), N->getOperand(0), LHS,
1241 GetScalarizedOp(N->getOperand(2)));
1245 //===----------------------------------------------------------------------===//
1246 // Operand Expansion
1247 //===----------------------------------------------------------------------===//
1249 /// ExpandOperand - This method is called when the specified operand of the
1250 /// specified node is found to need expansion. At this point, all of the result
1251 /// types of the node are known to be legal, but other operands of the node may
1252 /// need promotion or expansion as well as the specified one.
1253 bool DAGTypeLegalizer::ExpandOperand(SDNode *N, unsigned OpNo) {
1254 DEBUG(cerr << "Expand node operand: "; N->dump(&DAG); cerr << "\n");
1255 SDOperand Res(0, 0);
1257 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
1258 TargetLowering::Custom)
1259 Res = TLI.LowerOperation(SDOperand(N, 0), DAG);
1262 switch (N->getOpcode()) {
1265 cerr << "ExpandOperand Op #" << OpNo << ": ";
1266 N->dump(&DAG); cerr << "\n";
1268 assert(0 && "Do not know how to expand this operator's operand!");
1271 case ISD::TRUNCATE: Res = ExpandOperand_TRUNCATE(N); break;
1272 case ISD::BIT_CONVERT: Res = ExpandOperand_BIT_CONVERT(N); break;
1274 case ISD::SINT_TO_FP:
1275 Res = ExpandOperand_SINT_TO_FP(N->getOperand(0), N->getValueType(0));
1277 case ISD::UINT_TO_FP:
1278 Res = ExpandOperand_UINT_TO_FP(N->getOperand(0), N->getValueType(0));
1280 case ISD::EXTRACT_ELEMENT: Res = ExpandOperand_EXTRACT_ELEMENT(N); break;
1281 case ISD::SETCC: Res = ExpandOperand_SETCC(N); break;
1284 Res = ExpandOperand_STORE(cast<StoreSDNode>(N), OpNo);
1288 case ISD::MEMMOVE: Res = HandleMemIntrinsic(N); break;
1292 // If the result is null, the sub-method took care of registering results etc.
1293 if (!Res.Val) return false;
1294 // If the result is N, the sub-method updated N in place. Check to see if any
1295 // operands are new, and if so, mark them.
1297 // Mark N as new and remark N and its operands. This allows us to correctly
1298 // revisit N if it needs another step of promotion and allows us to visit
1299 // any new operands to N.
1300 N->setNodeId(NewNode);
1305 assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1306 "Invalid operand expansion");
1308 ReplaceValueWith(SDOperand(N, 0), Res);
1312 SDOperand DAGTypeLegalizer::ExpandOperand_TRUNCATE(SDNode *N) {
1314 GetExpandedOp(N->getOperand(0), InL, InH);
1315 // Just truncate the low part of the source.
1316 return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), InL);
1319 SDOperand DAGTypeLegalizer::ExpandOperand_BIT_CONVERT(SDNode *N) {
1320 return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
1323 SDOperand DAGTypeLegalizer::ExpandOperand_SINT_TO_FP(SDOperand Source,
1324 MVT::ValueType DestTy) {
1325 // We know the destination is legal, but that the input needs to be expanded.
1326 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
1328 // Check to see if the target has a custom way to lower this. If so, use it.
1329 switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
1330 default: assert(0 && "This action not implemented for this operation!");
1331 case TargetLowering::Legal:
1332 case TargetLowering::Expand:
1333 break; // This case is handled below.
1334 case TargetLowering::Custom:
1335 SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
1337 if (NV.Val) return NV;
1338 break; // The target lowered this.
1342 if (DestTy == MVT::f32)
1343 LC = RTLIB::SINTTOFP_I64_F32;
1345 assert(DestTy == MVT::f64 && "Unknown fp value type!");
1346 LC = RTLIB::SINTTOFP_I64_F64;
1349 assert(0 && "FIXME: no libcalls yet!");
1352 assert(TLI.getLibcallName(LC) && "Don't know how to expand this SINT_TO_FP!");
1353 Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
1354 SDOperand UnusedHiPart;
1355 return ExpandLibCall(TLI.getLibcallName(LC), Source.Val, true, UnusedHiPart);
1359 SDOperand DAGTypeLegalizer::ExpandOperand_UINT_TO_FP(SDOperand Source,
1360 MVT::ValueType DestTy) {
1361 // We know the destination is legal, but that the input needs to be expanded.
1362 assert(getTypeAction(Source.getValueType()) == Expand &&
1363 "This is not an expansion!");
1364 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
1366 // If this is unsigned, and not supported, first perform the conversion to
1367 // signed, then adjust the result if the sign bit is set.
1368 SDOperand SignedConv = ExpandOperand_SINT_TO_FP(Source, DestTy);
1370 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
1371 // incoming integer is set. To handle this, we dynamically test to see if
1372 // it is set, and, if so, add a fudge factor.
1374 GetExpandedOp(Source, Lo, Hi);
1376 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
1377 DAG.getConstant(0, Hi.getValueType()),
1379 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
1380 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
1381 SignSet, Four, Zero);
1382 uint64_t FF = 0x5f800000ULL;
1383 if (TLI.isLittleEndian()) FF <<= 32;
1384 Constant *FudgeFactor = ConstantInt::get(Type::Int64Ty, FF);
1386 SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
1387 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
1388 SDOperand FudgeInReg;
1389 if (DestTy == MVT::f32)
1390 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0);
1391 else if (MVT::getSizeInBits(DestTy) > MVT::getSizeInBits(MVT::f32))
1392 // FIXME: Avoid the extend by construction the right constantpool?
1393 FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, DestTy, DAG.getEntryNode(),
1394 CPIdx, NULL, 0, MVT::f32);
1396 assert(0 && "Unexpected conversion");
1398 return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
1401 SDOperand DAGTypeLegalizer::ExpandOperand_EXTRACT_ELEMENT(SDNode *N) {
1403 GetExpandedOp(N->getOperand(0), Lo, Hi);
1404 return cast<ConstantSDNode>(N->getOperand(1))->getValue() ? Hi : Lo;
1407 SDOperand DAGTypeLegalizer::ExpandOperand_SETCC(SDNode *N) {
1408 SDOperand NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
1409 ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
1410 ExpandSetCCOperands(NewLHS, NewRHS, CCCode);
1412 // If ExpandSetCCOperands returned a scalar, use it.
1413 if (NewRHS.Val == 0) return NewLHS;
1415 // Otherwise, update N to have the operands specified.
1416 return DAG.UpdateNodeOperands(SDOperand(N, 0), NewLHS, NewRHS,
1417 DAG.getCondCode(CCCode));
1420 /// ExpandSetCCOperands - Expand the operands of a comparison. This code is
1421 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
1422 void DAGTypeLegalizer::ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS,
1423 ISD::CondCode &CCCode) {
1424 SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
1425 GetExpandedOp(NewLHS, LHSLo, LHSHi);
1426 GetExpandedOp(NewRHS, RHSLo, RHSHi);
1428 MVT::ValueType VT = NewLHS.getValueType();
1429 if (VT == MVT::f32 || VT == MVT::f64) {
1430 assert(0 && "FIXME: softfp not implemented yet! should be promote not exp");
1433 if (VT == MVT::ppcf128) {
1434 // FIXME: This generated code sucks. We want to generate
1435 // FCMP crN, hi1, hi2
1437 // FCMP crN, lo1, lo2
1438 // The following can be improved, but not that much.
1439 SDOperand Tmp1, Tmp2, Tmp3;
1440 Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
1441 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, CCCode);
1442 Tmp3 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
1443 Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETNE);
1444 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, CCCode);
1445 Tmp1 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2);
1446 NewLHS = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp3);
1447 NewRHS = SDOperand(); // LHS is the result, not a compare.
1452 if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
1454 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
1455 if (RHSCST->isAllOnesValue()) {
1456 // Equality comparison to -1.
1457 NewLHS = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
1462 NewLHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
1463 NewRHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
1464 NewLHS = DAG.getNode(ISD::OR, NewLHS.getValueType(), NewLHS, NewRHS);
1465 NewRHS = DAG.getConstant(0, NewLHS.getValueType());
1469 // If this is a comparison of the sign bit, just look at the top part.
1471 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
1472 if ((CCCode == ISD::SETLT && CST->getValue() == 0) || // X < 0
1473 (CCCode == ISD::SETGT && CST->isAllOnesValue())) { // X > -1
1479 // FIXME: This generated code sucks.
1480 ISD::CondCode LowCC;
1482 default: assert(0 && "Unknown integer setcc!");
1484 case ISD::SETULT: LowCC = ISD::SETULT; break;
1486 case ISD::SETUGT: LowCC = ISD::SETUGT; break;
1488 case ISD::SETULE: LowCC = ISD::SETULE; break;
1490 case ISD::SETUGE: LowCC = ISD::SETUGE; break;
1493 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison
1494 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands
1495 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
1497 // NOTE: on targets without efficient SELECT of bools, we can always use
1498 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
1499 TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, false, true, NULL);
1500 SDOperand Tmp1, Tmp2;
1501 Tmp1 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC,
1502 false, DagCombineInfo);
1504 Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
1505 Tmp2 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi,
1506 CCCode, false, DagCombineInfo);
1508 Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi,
1509 DAG.getCondCode(CCCode));
1511 ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.Val);
1512 ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.Val);
1513 if ((Tmp1C && Tmp1C->getValue() == 0) ||
1514 (Tmp2C && Tmp2C->getValue() == 0 &&
1515 (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
1516 CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
1517 (Tmp2C && Tmp2C->getValue() == 1 &&
1518 (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
1519 CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
1520 // low part is known false, returns high part.
1521 // For LE / GE, if high part is known false, ignore the low part.
1522 // For LT / GT, if high part is known true, ignore the low part.
1524 NewRHS = SDOperand();
1528 NewLHS = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi,
1529 ISD::SETEQ, false, DagCombineInfo);
1531 NewLHS = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
1532 NewLHS = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
1533 NewLHS, Tmp1, Tmp2);
1534 NewRHS = SDOperand();
1537 SDOperand DAGTypeLegalizer::ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo) {
1538 assert(OpNo == 1 && "Can only expand the stored value so far");
1540 MVT::ValueType VT = N->getOperand(1).getValueType();
1541 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1542 SDOperand Ch = N->getChain();
1543 SDOperand Ptr = N->getBasePtr();
1544 int SVOffset = N->getSrcValueOffset();
1545 unsigned Alignment = N->getAlignment();
1546 bool isVolatile = N->isVolatile();
1549 assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!");
1551 if (!N->isTruncatingStore()) {
1552 unsigned IncrementSize = 0;
1554 // If this is a vector type, then we have to calculate the increment as
1555 // the product of the element size in bytes, and the number of elements
1556 // in the high half of the vector.
1557 if (MVT::isVector(N->getValue().getValueType())) {
1558 assert(0 && "Vectors not supported yet");
1560 SDNode *InVal = ST->getValue().Val;
1561 unsigned NumElems = MVT::getVectorNumElements(InVal->getValueType(0));
1562 MVT::ValueType EVT = MVT::getVectorElementType(InVal->getValueType(0));
1564 // Figure out if there is a simple type corresponding to this Vector
1565 // type. If so, convert to the vector type.
1566 MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1567 if (TLI.isTypeLegal(TVT)) {
1568 // Turn this into a normal store of the vector type.
1569 Tmp3 = LegalizeOp(Node->getOperand(1));
1570 Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1571 SVOffset, isVolatile, Alignment);
1572 Result = LegalizeOp(Result);
1574 } else if (NumElems == 1) {
1575 // Turn this into a normal store of the scalar type.
1576 Tmp3 = ScalarizeVectorOp(Node->getOperand(1));
1577 Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1578 SVOffset, isVolatile, Alignment);
1579 // The scalarized value type may not be legal, e.g. it might require
1580 // promotion or expansion. Relegalize the scalar store.
1581 return LegalizeOp(Result);
1583 SplitVectorOp(Node->getOperand(1), Lo, Hi);
1584 IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8;
1588 GetExpandedOp(N->getValue(), Lo, Hi);
1589 IncrementSize = Hi.Val ? MVT::getSizeInBits(Hi.getValueType())/8 : 0;
1591 if (!TLI.isLittleEndian())
1595 Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(),
1596 SVOffset, isVolatile, Alignment);
1598 assert(Hi.Val && "FIXME: int <-> float should be handled with promote!");
1600 if (Hi.Val == NULL) {
1601 // Must be int <-> float one-to-one expansion.
1606 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1607 getIntPtrConstant(IncrementSize));
1608 assert(isTypeLegal(Ptr.getValueType()) && "Pointers must be legal!");
1609 Hi = DAG.getStore(Ch, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize,
1610 isVolatile, MinAlign(Alignment, IncrementSize));
1611 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1612 } else if (MVT::getSizeInBits(N->getStoredVT()) <= MVT::getSizeInBits(NVT)) {
1613 GetExpandedOp(N->getValue(), Lo, Hi);
1614 return DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
1615 N->getStoredVT(), isVolatile, Alignment);
1616 } else if (TLI.isLittleEndian()) {
1617 // Little-endian - low bits are at low addresses.
1618 GetExpandedOp(N->getValue(), Lo, Hi);
1620 Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset,
1621 isVolatile, Alignment);
1623 unsigned ExcessBits =
1624 MVT::getSizeInBits(N->getStoredVT()) - MVT::getSizeInBits(NVT);
1625 MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits);
1627 // Increment the pointer to the other half.
1628 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
1629 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1630 getIntPtrConstant(IncrementSize));
1631 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1632 SVOffset+IncrementSize, NEVT,
1633 isVolatile, MinAlign(Alignment, IncrementSize));
1634 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1636 // Big-endian - high bits are at low addresses. Favor aligned stores at
1637 // the cost of some bit-fiddling.
1638 GetExpandedOp(N->getValue(), Lo, Hi);
1640 MVT::ValueType EVT = N->getStoredVT();
1641 unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8;
1642 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8;
1643 unsigned ExcessBits = (EBytes - IncrementSize)*8;
1644 MVT::ValueType HiVT =
1645 MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits);
1647 if (ExcessBits < MVT::getSizeInBits(NVT)) {
1648 // Transfer high bits from the top of Lo to the bottom of Hi.
1649 Hi = DAG.getNode(ISD::SHL, NVT, Hi,
1650 DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits,
1651 TLI.getShiftAmountTy()));
1652 Hi = DAG.getNode(ISD::OR, NVT, Hi,
1653 DAG.getNode(ISD::SRL, NVT, Lo,
1654 DAG.getConstant(ExcessBits,
1655 TLI.getShiftAmountTy())));
1658 // Store both the high bits and maybe some of the low bits.
1659 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(),
1660 SVOffset, HiVT, isVolatile, Alignment);
1662 // Increment the pointer to the other half.
1663 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1664 getIntPtrConstant(IncrementSize));
1665 // Store the lowest ExcessBits bits in the second half.
1666 Lo = DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(),
1667 SVOffset+IncrementSize,
1668 MVT::getIntegerType(ExcessBits),
1669 isVolatile, MinAlign(Alignment, IncrementSize));
1670 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1674 //===----------------------------------------------------------------------===//
1675 // Operand Vector Scalarization <1 x ty> -> ty.
1676 //===----------------------------------------------------------------------===//
1678 bool DAGTypeLegalizer::ScalarizeOperand(SDNode *N, unsigned OpNo) {
1679 DEBUG(cerr << "Scalarize node operand " << OpNo << ": "; N->dump(&DAG);
1681 SDOperand Res(0, 0);
1683 // FIXME: Should we support custom lowering for scalarization?
1685 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
1686 TargetLowering::Custom)
1687 Res = TLI.LowerOperation(SDOperand(N, 0), DAG);
1691 switch (N->getOpcode()) {
1694 cerr << "ScalarizeOperand Op #" << OpNo << ": ";
1695 N->dump(&DAG); cerr << "\n";
1697 assert(0 && "Do not know how to scalarize this operator's operand!");
1700 case ISD::EXTRACT_VECTOR_ELT:
1701 Res = ScalarizeOp_EXTRACT_VECTOR_ELT(N, OpNo);
1706 // If the result is null, the sub-method took care of registering results etc.
1707 if (!Res.Val) return false;
1709 // If the result is N, the sub-method updated N in place. Check to see if any
1710 // operands are new, and if so, mark them.
1712 // Mark N as new and remark N and its operands. This allows us to correctly
1713 // revisit N if it needs another step of promotion and allows us to visit
1714 // any new operands to N.
1715 N->setNodeId(NewNode);
1720 assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
1721 "Invalid operand expansion");
1723 ReplaceValueWith(SDOperand(N, 0), Res);
1727 /// ScalarizeOp_EXTRACT_VECTOR_ELT - If the input is a vector that needs to be
1728 /// scalarized, it must be <1 x ty>, just return the operand, ignoring the
1730 SDOperand DAGTypeLegalizer::ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N,
1732 return GetScalarizedOp(N->getOperand(0));
1736 //===----------------------------------------------------------------------===//
1738 //===----------------------------------------------------------------------===//
1740 /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
1741 /// only uses types natively supported by the target.
1743 /// Note that this is an involved process that may invalidate pointers into
1745 void SelectionDAG::LegalizeTypes() {
1746 DAGTypeLegalizer(*this).run();