1 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SelectionDAG::Legalize method.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "llvm/CodeGen/MachineConstantPool.h"
16 #include "llvm/CodeGen/MachineFunction.h"
17 #include "llvm/CodeGen/MachineFrameInfo.h"
18 #include "llvm/Target/TargetLowering.h"
19 #include "llvm/Target/TargetData.h"
20 #include "llvm/Target/TargetOptions.h"
21 #include "llvm/CallingConv.h"
22 #include "llvm/Constants.h"
26 //===----------------------------------------------------------------------===//
27 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
28 /// hacks on it until the target machine can handle it. This involves
29 /// eliminating value sizes the machine cannot handle (promoting small sizes to
30 /// large sizes or splitting up large values into small values) as well as
31 /// eliminating operations the machine cannot handle.
33 /// This code also does a small amount of optimization and recognition of idioms
34 /// as part of its processing. For example, if a target does not support a
35 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
36 /// will attempt merge setcc and brc instructions into brcc's.
39 class SelectionDAGLegalize {
43 /// LegalizeAction - This enum indicates what action we should take for each
44 /// value type the can occur in the program.
46 Legal, // The target natively supports this value type.
47 Promote, // This should be promoted to the next larger type.
48 Expand, // This integer type should be broken into smaller pieces.
51 /// ValueTypeActions - This is a bitvector that contains two bits for each
52 /// value type, where the two bits correspond to the LegalizeAction enum.
53 /// This can be queried with "getTypeAction(VT)".
54 unsigned ValueTypeActions;
56 /// NeedsAnotherIteration - This is set when we expand a large integer
57 /// operation into smaller integer operations, but the smaller operations are
58 /// not set. This occurs only rarely in practice, for targets that don't have
59 /// 32-bit or larger integer registers.
60 bool NeedsAnotherIteration;
62 /// LegalizedNodes - For nodes that are of legal width, and that have more
63 /// than one use, this map indicates what regularized operand to use. This
64 /// allows us to avoid legalizing the same thing more than once.
65 std::map<SDOperand, SDOperand> LegalizedNodes;
67 /// PromotedNodes - For nodes that are below legal width, and that have more
68 /// than one use, this map indicates what promoted value to use. This allows
69 /// us to avoid promoting the same thing more than once.
70 std::map<SDOperand, SDOperand> PromotedNodes;
72 /// ExpandedNodes - For nodes that need to be expanded, and which have more
73 /// than one use, this map indicates which which operands are the expanded
74 /// version of the input. This allows us to avoid expanding the same node
76 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
78 void AddLegalizedOperand(SDOperand From, SDOperand To) {
79 bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second;
80 assert(isNew && "Got into the map somehow?");
82 void AddPromotedOperand(SDOperand From, SDOperand To) {
83 bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
84 assert(isNew && "Got into the map somehow?");
89 SelectionDAGLegalize(SelectionDAG &DAG);
91 /// Run - While there is still lowering to do, perform a pass over the DAG.
92 /// Most regularization can be done in a single pass, but targets that require
93 /// large values to be split into registers multiple times (e.g. i64 -> 4x
94 /// i16) require iteration for these values (the first iteration will demote
95 /// to i32, the second will demote to i16).
98 NeedsAnotherIteration = false;
100 } while (NeedsAnotherIteration);
103 /// getTypeAction - Return how we should legalize values of this type, either
104 /// it is already legal or we need to expand it into multiple registers of
105 /// smaller integer type, or we need to promote it to a larger type.
106 LegalizeAction getTypeAction(MVT::ValueType VT) const {
107 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3);
110 /// isTypeLegal - Return true if this type is legal on this target.
112 bool isTypeLegal(MVT::ValueType VT) const {
113 return getTypeAction(VT) == Legal;
119 SDOperand LegalizeOp(SDOperand O);
120 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
121 SDOperand PromoteOp(SDOperand O);
123 SDOperand ExpandLibCall(const char *Name, SDNode *Node,
125 SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
128 SDOperand ExpandLegalUINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT);
129 SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT,
132 bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
133 SDOperand &Lo, SDOperand &Hi);
134 void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
135 SDOperand &Lo, SDOperand &Hi);
136 void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
137 SDOperand &Lo, SDOperand &Hi);
139 void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain);
141 SDOperand getIntPtrConstant(uint64_t Val) {
142 return DAG.getConstant(Val, TLI.getPointerTy());
148 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
149 : TLI(dag.getTargetLoweringInfo()), DAG(dag),
150 ValueTypeActions(TLI.getValueTypeActions()) {
151 assert(MVT::LAST_VALUETYPE <= 16 &&
152 "Too many value types for ValueTypeActions to hold!");
155 /// ExpandLegalUINT_TO_FP - This function is responsible for legalizing a
156 /// UINT_TO_FP operation of the specified operand when the target requests that
157 /// we expand it. At this point, we know that the result and operand types are
158 /// legal for the target.
159 SDOperand SelectionDAGLegalize::ExpandLegalUINT_TO_FP(SDOperand Op0,
160 MVT::ValueType DestVT) {
161 SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0);
163 SDOperand SignSet = DAG.getSetCC(ISD::SETLT, TLI.getSetCCResultTy(),
166 Op0.getValueType()));
167 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
168 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
169 SignSet, Four, Zero);
171 // If the sign bit of the integer is set, the large number will be treated as
172 // a negative number. To counteract this, the dynamic code adds an offset
173 // depending on the data type.
175 switch (Op0.getValueType()) {
176 default: assert(0 && "Unsupported integer type!");
177 case MVT::i8 : FF = 0x43800000ULL; break; // 2^8 (as a float)
178 case MVT::i16: FF = 0x47800000ULL; break; // 2^16 (as a float)
179 case MVT::i32: FF = 0x4F800000ULL; break; // 2^32 (as a float)
180 case MVT::i64: FF = 0x5F800000ULL; break; // 2^64 (as a float)
182 if (TLI.isLittleEndian()) FF <<= 32;
183 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
185 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
186 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor),
188 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
189 SDOperand FudgeInReg;
190 if (DestVT == MVT::f32)
191 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
192 DAG.getSrcValue(NULL));
194 assert(DestVT == MVT::f64 && "Unexpected conversion");
195 FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64,
196 DAG.getEntryNode(), CPIdx,
197 DAG.getSrcValue(NULL), MVT::f32));
200 NeedsAnotherIteration = true;
201 return DAG.getNode(ISD::ADD, DestVT, Tmp1, FudgeInReg);
204 /// PromoteLegalUINT_TO_FP - This function is responsible for legalizing a
205 /// UINT_TO_FP operation of the specified operand when the target requests that
206 /// we promote it. At this point, we know that the result and operand types are
207 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
208 /// operation that takes a larger input.
209 SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp,
210 MVT::ValueType DestVT,
212 // First step, figure out the appropriate *INT_TO_FP operation to use.
213 MVT::ValueType NewInTy = LegalOp.getValueType();
215 unsigned OpToUse = 0;
217 // Scan for the appropriate larger type to use.
219 NewInTy = (MVT::ValueType)(NewInTy+1);
220 assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!");
222 // If the target supports SINT_TO_FP of this type, use it.
223 switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
225 case TargetLowering::Legal:
226 if (!TLI.hasNativeSupportFor(NewInTy))
227 break; // Can't use this datatype.
229 case TargetLowering::Custom:
230 OpToUse = ISD::SINT_TO_FP;
234 if (isSigned) continue;
236 // If the target supports UINT_TO_FP of this type, use it.
237 switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
239 case TargetLowering::Legal:
240 if (!TLI.hasNativeSupportFor(NewInTy))
241 break; // Can't use this datatype.
243 case TargetLowering::Custom:
244 OpToUse = ISD::UINT_TO_FP;
249 // Otherwise, try a larger type.
252 // Make sure to legalize any nodes we create here in the next pass.
253 NeedsAnotherIteration = true;
255 // Okay, we found the operation and type to use. Zero extend our input to the
256 // desired type then run the operation on it.
257 return DAG.getNode(OpToUse, DestVT,
258 DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
262 void SelectionDAGLegalize::LegalizeDAG() {
263 SDOperand OldRoot = DAG.getRoot();
264 SDOperand NewRoot = LegalizeOp(OldRoot);
265 DAG.setRoot(NewRoot);
267 ExpandedNodes.clear();
268 LegalizedNodes.clear();
269 PromotedNodes.clear();
271 // Remove dead nodes now.
272 DAG.RemoveDeadNodes(OldRoot.Val);
275 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
276 assert(getTypeAction(Op.getValueType()) == Legal &&
277 "Caller should expand or promote operands that are not legal!");
278 SDNode *Node = Op.Val;
280 // If this operation defines any values that cannot be represented in a
281 // register on this target, make sure to expand or promote them.
282 if (Node->getNumValues() > 1) {
283 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
284 switch (getTypeAction(Node->getValueType(i))) {
285 case Legal: break; // Nothing to do.
288 ExpandOp(Op.getValue(i), T1, T2);
289 assert(LegalizedNodes.count(Op) &&
290 "Expansion didn't add legal operands!");
291 return LegalizedNodes[Op];
294 PromoteOp(Op.getValue(i));
295 assert(LegalizedNodes.count(Op) &&
296 "Expansion didn't add legal operands!");
297 return LegalizedNodes[Op];
301 // Note that LegalizeOp may be reentered even from single-use nodes, which
302 // means that we always must cache transformed nodes.
303 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
304 if (I != LegalizedNodes.end()) return I->second;
306 SDOperand Tmp1, Tmp2, Tmp3;
308 SDOperand Result = Op;
310 switch (Node->getOpcode()) {
312 if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
313 // If this is a target node, legalize it by legalizing the operands then
314 // passing it through.
315 std::vector<SDOperand> Ops;
316 bool Changed = false;
317 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
318 Ops.push_back(LegalizeOp(Node->getOperand(i)));
319 Changed = Changed || Node->getOperand(i) != Ops.back();
322 if (Node->getNumValues() == 1)
323 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
325 std::vector<MVT::ValueType> VTs(Node->value_begin(),
327 Result = DAG.getNode(Node->getOpcode(), VTs, Ops);
330 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
331 AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
332 return Result.getValue(Op.ResNo);
334 // Otherwise this is an unhandled builtin node. splat.
335 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
336 assert(0 && "Do not know how to legalize this operator!");
338 case ISD::EntryToken:
339 case ISD::FrameIndex:
340 case ISD::GlobalAddress:
341 case ISD::ExternalSymbol:
342 case ISD::ConstantPool: // Nothing to do.
343 assert(getTypeAction(Node->getValueType(0)) == Legal &&
344 "This must be legal!");
346 case ISD::CopyFromReg:
347 Tmp1 = LegalizeOp(Node->getOperand(0));
348 if (Tmp1 != Node->getOperand(0))
349 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(),
350 Node->getValueType(0), Tmp1);
352 Result = Op.getValue(0);
354 // Since CopyFromReg produces two values, make sure to remember that we
355 // legalized both of them.
356 AddLegalizedOperand(Op.getValue(0), Result);
357 AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
358 return Result.getValue(Op.ResNo);
359 case ISD::ImplicitDef:
360 Tmp1 = LegalizeOp(Node->getOperand(0));
361 if (Tmp1 != Node->getOperand(0))
362 Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg());
365 MVT::ValueType VT = Op.getValueType();
366 switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
367 default: assert(0 && "This action is not supported yet!");
368 case TargetLowering::Expand:
369 case TargetLowering::Promote:
370 if (MVT::isInteger(VT))
371 Result = DAG.getConstant(0, VT);
372 else if (MVT::isFloatingPoint(VT))
373 Result = DAG.getConstantFP(0, VT);
375 assert(0 && "Unknown value type!");
377 case TargetLowering::Legal:
383 // We know we don't need to expand constants here, constants only have one
384 // value and we check that it is fine above.
386 // FIXME: Maybe we should handle things like targets that don't support full
387 // 32-bit immediates?
389 case ISD::ConstantFP: {
390 // Spill FP immediates to the constant pool if the target cannot directly
391 // codegen them. Targets often have some immediate values that can be
392 // efficiently generated into an FP register without a load. We explicitly
393 // leave these constants as ConstantFP nodes for the target to deal with.
395 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
397 // Check to see if this FP immediate is already legal.
398 bool isLegal = false;
399 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
400 E = TLI.legal_fpimm_end(); I != E; ++I)
401 if (CFP->isExactlyValue(*I)) {
407 // Otherwise we need to spill the constant to memory.
408 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
412 // If a FP immediate is precise when represented as a float, we put it
413 // into the constant pool as a float, even if it's is statically typed
415 MVT::ValueType VT = CFP->getValueType(0);
416 bool isDouble = VT == MVT::f64;
417 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
418 Type::FloatTy, CFP->getValue());
419 if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
420 // Only do this if the target has a native EXTLOAD instruction from
422 TLI.getOperationAction(ISD::EXTLOAD,
423 MVT::f32) == TargetLowering::Legal) {
424 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
429 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
432 Result = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
433 CPIdx, DAG.getSrcValue(NULL), MVT::f32);
435 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
436 DAG.getSrcValue(NULL));
441 case ISD::TokenFactor: {
442 std::vector<SDOperand> Ops;
443 bool Changed = false;
444 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
445 SDOperand Op = Node->getOperand(i);
446 // Fold single-use TokenFactor nodes into this token factor as we go.
447 // FIXME: This is something that the DAGCombiner should do!!
448 if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
450 for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
451 Ops.push_back(LegalizeOp(Op.getOperand(j)));
453 Ops.push_back(LegalizeOp(Op)); // Legalize the operands
454 Changed |= Ops[i] != Op;
458 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
462 case ISD::CALLSEQ_START:
463 case ISD::CALLSEQ_END:
464 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
465 // Do not try to legalize the target-specific arguments (#1+)
466 Tmp2 = Node->getOperand(0);
468 Node->setAdjCallChain(Tmp1);
470 // If moving the operand from pointing to Tmp2 dropped its use count to 1,
471 // this will cause the maps used to memoize results to get confused.
472 // Create and add a dummy use, just to increase its use count. This will
473 // be removed at the end of legalize when dead nodes are removed.
474 if (Tmp2.Val->hasOneUse())
475 DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2,
476 DAG.getConstant(0, MVT::i32));
478 // Note that we do not create new CALLSEQ_DOWN/UP nodes here. These
479 // nodes are treated specially and are mutated in place. This makes the dag
480 // legalization process more efficient and also makes libcall insertion
483 case ISD::DYNAMIC_STACKALLOC:
484 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
485 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size.
486 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment.
487 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
488 Tmp3 != Node->getOperand(2)) {
489 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
490 std::vector<SDOperand> Ops;
491 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
492 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops);
494 Result = Op.getValue(0);
496 // Since this op produces two values, make sure to remember that we
497 // legalized both of them.
498 AddLegalizedOperand(SDOperand(Node, 0), Result);
499 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
500 return Result.getValue(Op.ResNo);
504 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
505 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee.
507 bool Changed = false;
508 std::vector<SDOperand> Ops;
509 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
510 Ops.push_back(LegalizeOp(Node->getOperand(i)));
511 Changed |= Ops.back() != Node->getOperand(i);
514 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) {
515 std::vector<MVT::ValueType> RetTyVTs;
516 RetTyVTs.reserve(Node->getNumValues());
517 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
518 RetTyVTs.push_back(Node->getValueType(i));
519 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops,
520 Node->getOpcode() == ISD::TAILCALL), 0);
522 Result = Result.getValue(0);
524 // Since calls produce multiple values, make sure to remember that we
525 // legalized all of them.
526 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
527 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
528 return Result.getValue(Op.ResNo);
531 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
532 if (Tmp1 != Node->getOperand(0))
533 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
537 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
539 switch (getTypeAction(Node->getOperand(1).getValueType())) {
540 case Expand: assert(0 && "It's impossible to expand bools");
542 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
545 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition.
548 // Basic block destination (Op#2) is always legal.
549 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
550 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
551 Node->getOperand(2));
553 case ISD::BRCONDTWOWAY:
554 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
555 switch (getTypeAction(Node->getOperand(1).getValueType())) {
556 case Expand: assert(0 && "It's impossible to expand bools");
558 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
561 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition.
564 // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR
566 switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) {
567 case TargetLowering::Promote:
568 default: assert(0 && "This action is not supported yet!");
569 case TargetLowering::Legal:
570 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
571 std::vector<SDOperand> Ops;
574 Ops.push_back(Node->getOperand(2));
575 Ops.push_back(Node->getOperand(3));
576 Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops);
579 case TargetLowering::Expand:
580 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
581 Node->getOperand(2));
582 Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3));
588 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
589 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer.
591 if (Tmp1 != Node->getOperand(0) ||
592 Tmp2 != Node->getOperand(1))
593 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2,
594 Node->getOperand(2));
596 Result = SDOperand(Node, 0);
598 // Since loads produce two values, make sure to remember that we legalized
600 AddLegalizedOperand(SDOperand(Node, 0), Result);
601 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
602 return Result.getValue(Op.ResNo);
606 case ISD::ZEXTLOAD: {
607 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
608 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer.
610 MVT::ValueType SrcVT = cast<VTSDNode>(Node->getOperand(3))->getVT();
611 switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) {
612 default: assert(0 && "This action is not supported yet!");
613 case TargetLowering::Promote:
614 assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!");
615 Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0),
616 Tmp1, Tmp2, Node->getOperand(2), MVT::i8);
617 // Since loads produce two values, make sure to remember that we legalized
619 AddLegalizedOperand(SDOperand(Node, 0), Result);
620 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
621 return Result.getValue(Op.ResNo);
623 case TargetLowering::Legal:
624 if (Tmp1 != Node->getOperand(0) ||
625 Tmp2 != Node->getOperand(1))
626 Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0),
627 Tmp1, Tmp2, Node->getOperand(2), SrcVT);
629 Result = SDOperand(Node, 0);
631 // Since loads produce two values, make sure to remember that we legalized
633 AddLegalizedOperand(SDOperand(Node, 0), Result);
634 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
635 return Result.getValue(Op.ResNo);
636 case TargetLowering::Expand:
637 //f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
638 if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) {
639 SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, Node->getOperand(2));
640 Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load);
642 return Load.getValue(1);
645 assert(Node->getOpcode() != ISD::EXTLOAD &&
646 "EXTLOAD should always be supported!");
647 // Turn the unsupported load into an EXTLOAD followed by an explicit
648 // zero/sign extend inreg.
649 Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
650 Tmp1, Tmp2, Node->getOperand(2), SrcVT);
652 if (Node->getOpcode() == ISD::SEXTLOAD)
653 ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
654 Result, DAG.getValueType(SrcVT));
656 ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
657 AddLegalizedOperand(SDOperand(Node, 0), ValRes);
658 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
660 return Result.getValue(1);
663 assert(0 && "Unreachable");
665 case ISD::EXTRACT_ELEMENT:
666 // Get both the low and high parts.
667 ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
668 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
669 Result = Tmp2; // 1 -> Hi
671 Result = Tmp1; // 0 -> Lo
675 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
677 switch (getTypeAction(Node->getOperand(1).getValueType())) {
679 // Legalize the incoming value (must be legal).
680 Tmp2 = LegalizeOp(Node->getOperand(1));
681 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
682 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
685 Tmp2 = PromoteOp(Node->getOperand(1));
686 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
690 ExpandOp(Node->getOperand(1), Lo, Hi);
691 unsigned Reg = cast<RegSDNode>(Node)->getReg();
692 Lo = DAG.getCopyToReg(Tmp1, Lo, Reg);
693 Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1);
694 // Note that the copytoreg nodes are independent of each other.
695 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
696 assert(isTypeLegal(Result.getValueType()) &&
697 "Cannot expand multiple times yet (i64 -> i16)");
703 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
704 switch (Node->getNumOperands()) {
706 switch (getTypeAction(Node->getOperand(1).getValueType())) {
708 Tmp2 = LegalizeOp(Node->getOperand(1));
709 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
710 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
714 ExpandOp(Node->getOperand(1), Lo, Hi);
715 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
719 Tmp2 = PromoteOp(Node->getOperand(1));
720 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
725 if (Tmp1 != Node->getOperand(0))
726 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
728 default: { // ret <values>
729 std::vector<SDOperand> NewValues;
730 NewValues.push_back(Tmp1);
731 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
732 switch (getTypeAction(Node->getOperand(i).getValueType())) {
734 NewValues.push_back(LegalizeOp(Node->getOperand(i)));
738 ExpandOp(Node->getOperand(i), Lo, Hi);
739 NewValues.push_back(Lo);
740 NewValues.push_back(Hi);
744 assert(0 && "Can't promote multiple return value yet!");
746 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
752 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
753 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer.
755 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
756 if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
757 if (CFP->getValueType(0) == MVT::f32) {
762 V.F = CFP->getValue();
763 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
764 DAG.getConstant(V.I, MVT::i32), Tmp2,
765 Node->getOperand(3));
767 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
772 V.F = CFP->getValue();
773 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
774 DAG.getConstant(V.I, MVT::i64), Tmp2,
775 Node->getOperand(3));
780 switch (getTypeAction(Node->getOperand(1).getValueType())) {
782 SDOperand Val = LegalizeOp(Node->getOperand(1));
783 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
784 Tmp2 != Node->getOperand(2))
785 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2,
786 Node->getOperand(3));
790 // Truncate the value and store the result.
791 Tmp3 = PromoteOp(Node->getOperand(1));
792 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
794 DAG.getValueType(Node->getOperand(1).getValueType()));
799 ExpandOp(Node->getOperand(1), Lo, Hi);
801 if (!TLI.isLittleEndian())
804 Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2,
805 Node->getOperand(3));
806 unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
807 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
808 getIntPtrConstant(IncrementSize));
809 assert(isTypeLegal(Tmp2.getValueType()) &&
810 "Pointers must be legal!");
811 //Again, claiming both parts of the store came form the same Instr
812 Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2,
813 Node->getOperand(3));
814 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
819 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
820 if (Tmp1 != Node->getOperand(0))
821 Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1));
823 case ISD::TRUNCSTORE:
824 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
825 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer.
827 switch (getTypeAction(Node->getOperand(1).getValueType())) {
829 Tmp2 = LegalizeOp(Node->getOperand(1));
830 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
831 Tmp3 != Node->getOperand(2))
832 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
833 Node->getOperand(3), Node->getOperand(4));
837 assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
841 switch (getTypeAction(Node->getOperand(0).getValueType())) {
842 case Expand: assert(0 && "It's impossible to expand bools");
844 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
847 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
850 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal
851 Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal
853 switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) {
854 default: assert(0 && "This action is not supported yet!");
855 case TargetLowering::Legal:
856 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
857 Tmp3 != Node->getOperand(2))
858 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0),
861 case TargetLowering::Promote: {
863 TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
864 unsigned ExtOp, TruncOp;
865 if (MVT::isInteger(Tmp2.getValueType())) {
866 ExtOp = ISD::ZERO_EXTEND;
867 TruncOp = ISD::TRUNCATE;
869 ExtOp = ISD::FP_EXTEND;
870 TruncOp = ISD::FP_ROUND;
872 // Promote each of the values to the new type.
873 Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
874 Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
875 // Perform the larger operation, then round down.
876 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
877 Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
883 switch (getTypeAction(Node->getOperand(0).getValueType())) {
885 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS
886 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS
887 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
888 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
889 Node->getValueType(0), Tmp1, Tmp2);
892 Tmp1 = PromoteOp(Node->getOperand(0)); // LHS
893 Tmp2 = PromoteOp(Node->getOperand(1)); // RHS
895 // If this is an FP compare, the operands have already been extended.
896 if (MVT::isInteger(Node->getOperand(0).getValueType())) {
897 MVT::ValueType VT = Node->getOperand(0).getValueType();
898 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
900 // Otherwise, we have to insert explicit sign or zero extends. Note
901 // that we could insert sign extends for ALL conditions, but zero extend
902 // is cheaper on many machines (an AND instead of two shifts), so prefer
904 switch (cast<SetCCSDNode>(Node)->getCondition()) {
905 default: assert(0 && "Unknown integer comparison!");
912 // ALL of these operations will work if we either sign or zero extend
913 // the operands (including the unsigned comparisons!). Zero extend is
914 // usually a simpler/cheaper operation, so prefer it.
915 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
916 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
922 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
923 DAG.getValueType(VT));
924 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
925 DAG.getValueType(VT));
930 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
931 Node->getValueType(0), Tmp1, Tmp2);
934 SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
935 ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
936 ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
937 switch (cast<SetCCSDNode>(Node)->getCondition()) {
941 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
942 if (RHSCST->isAllOnesValue()) {
944 Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
945 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
946 Node->getValueType(0), Tmp1, RHSLo);
950 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
951 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
952 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
953 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
954 Node->getValueType(0), Tmp1,
955 DAG.getConstant(0, Tmp1.getValueType()));
958 // If this is a comparison of the sign bit, just look at the top part.
960 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1)))
961 if ((cast<SetCCSDNode>(Node)->getCondition() == ISD::SETLT &&
962 CST->getValue() == 0) || // X < 0
963 (cast<SetCCSDNode>(Node)->getCondition() == ISD::SETGT &&
964 (CST->isAllOnesValue()))) // X > -1
965 return DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
966 Node->getValueType(0), LHSHi, RHSHi);
968 // FIXME: This generated code sucks.
970 switch (cast<SetCCSDNode>(Node)->getCondition()) {
971 default: assert(0 && "Unknown integer setcc!");
973 case ISD::SETULT: LowCC = ISD::SETULT; break;
975 case ISD::SETUGT: LowCC = ISD::SETUGT; break;
977 case ISD::SETULE: LowCC = ISD::SETULE; break;
979 case ISD::SETUGE: LowCC = ISD::SETUGE; break;
982 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison
983 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands
984 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
986 // NOTE: on targets without efficient SELECT of bools, we can always use
987 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
988 Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo);
989 Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
990 Node->getValueType(0), LHSHi, RHSHi);
991 Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi);
992 Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
1001 case ISD::MEMMOVE: {
1002 Tmp1 = LegalizeOp(Node->getOperand(0)); // Chain
1003 Tmp2 = LegalizeOp(Node->getOperand(1)); // Pointer
1005 if (Node->getOpcode() == ISD::MEMSET) { // memset = ubyte
1006 switch (getTypeAction(Node->getOperand(2).getValueType())) {
1007 case Expand: assert(0 && "Cannot expand a byte!");
1009 Tmp3 = LegalizeOp(Node->getOperand(2));
1012 Tmp3 = PromoteOp(Node->getOperand(2));
1016 Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer,
1020 switch (getTypeAction(Node->getOperand(3).getValueType())) {
1022 // Length is too big, just take the lo-part of the length.
1024 ExpandOp(Node->getOperand(3), HiPart, Tmp4);
1028 Tmp4 = LegalizeOp(Node->getOperand(3));
1031 Tmp4 = PromoteOp(Node->getOperand(3));
1036 switch (getTypeAction(Node->getOperand(4).getValueType())) { // uint
1037 case Expand: assert(0 && "Cannot expand this yet!");
1039 Tmp5 = LegalizeOp(Node->getOperand(4));
1042 Tmp5 = PromoteOp(Node->getOperand(4));
1046 switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
1047 default: assert(0 && "This action not implemented for this operation!");
1048 case TargetLowering::Legal:
1049 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1050 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
1051 Tmp5 != Node->getOperand(4)) {
1052 std::vector<SDOperand> Ops;
1053 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
1054 Ops.push_back(Tmp4); Ops.push_back(Tmp5);
1055 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
1058 case TargetLowering::Expand: {
1059 // Otherwise, the target does not support this operation. Lower the
1060 // operation to an explicit libcall as appropriate.
1061 MVT::ValueType IntPtr = TLI.getPointerTy();
1062 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
1063 std::vector<std::pair<SDOperand, const Type*> > Args;
1065 const char *FnName = 0;
1066 if (Node->getOpcode() == ISD::MEMSET) {
1067 Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1068 // Extend the ubyte argument to be an int value for the call.
1069 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
1070 Args.push_back(std::make_pair(Tmp3, Type::IntTy));
1071 Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1074 } else if (Node->getOpcode() == ISD::MEMCPY ||
1075 Node->getOpcode() == ISD::MEMMOVE) {
1076 Args.push_back(std::make_pair(Tmp2, IntPtrTy));
1077 Args.push_back(std::make_pair(Tmp3, IntPtrTy));
1078 Args.push_back(std::make_pair(Tmp4, IntPtrTy));
1079 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
1081 assert(0 && "Unknown op!");
1084 std::pair<SDOperand,SDOperand> CallResult =
1085 TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false,
1086 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
1087 Result = CallResult.second;
1088 NeedsAnotherIteration = true;
1091 case TargetLowering::Custom:
1092 std::vector<SDOperand> Ops;
1093 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
1094 Ops.push_back(Tmp4); Ops.push_back(Tmp5);
1095 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
1096 Result = TLI.LowerOperation(Result, DAG);
1097 Result = LegalizeOp(Result);
1104 Tmp1 = LegalizeOp(Node->getOperand(0));
1105 Tmp2 = LegalizeOp(Node->getOperand(1));
1107 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
1108 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
1109 std::vector<SDOperand> Ops;
1110 Ops.push_back(Tmp1);
1111 Ops.push_back(Tmp2);
1112 Result = DAG.getNode(ISD::READPORT, VTs, Ops);
1114 Result = SDOperand(Node, 0);
1115 // Since these produce two values, make sure to remember that we legalized
1117 AddLegalizedOperand(SDOperand(Node, 0), Result);
1118 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1119 return Result.getValue(Op.ResNo);
1120 case ISD::WRITEPORT:
1121 Tmp1 = LegalizeOp(Node->getOperand(0));
1122 Tmp2 = LegalizeOp(Node->getOperand(1));
1123 Tmp3 = LegalizeOp(Node->getOperand(2));
1124 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1125 Tmp3 != Node->getOperand(2))
1126 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
1130 Tmp1 = LegalizeOp(Node->getOperand(0));
1131 Tmp2 = LegalizeOp(Node->getOperand(1));
1133 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1134 case TargetLowering::Custom:
1135 default: assert(0 && "This action not implemented for this operation!");
1136 case TargetLowering::Legal:
1137 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
1138 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
1139 std::vector<SDOperand> Ops;
1140 Ops.push_back(Tmp1);
1141 Ops.push_back(Tmp2);
1142 Result = DAG.getNode(ISD::READPORT, VTs, Ops);
1144 Result = SDOperand(Node, 0);
1146 case TargetLowering::Expand:
1147 // Replace this with a load from memory.
1148 Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0),
1149 Node->getOperand(1), DAG.getSrcValue(NULL));
1150 Result = LegalizeOp(Result);
1154 // Since these produce two values, make sure to remember that we legalized
1156 AddLegalizedOperand(SDOperand(Node, 0), Result);
1157 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1158 return Result.getValue(Op.ResNo);
1161 Tmp1 = LegalizeOp(Node->getOperand(0));
1162 Tmp2 = LegalizeOp(Node->getOperand(1));
1163 Tmp3 = LegalizeOp(Node->getOperand(2));
1165 switch (TLI.getOperationAction(Node->getOpcode(),
1166 Node->getOperand(1).getValueType())) {
1167 case TargetLowering::Custom:
1168 default: assert(0 && "This action not implemented for this operation!");
1169 case TargetLowering::Legal:
1170 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
1171 Tmp3 != Node->getOperand(2))
1172 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
1174 case TargetLowering::Expand:
1175 // Replace this with a store to memory.
1176 Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0),
1177 Node->getOperand(1), Node->getOperand(2),
1178 DAG.getSrcValue(NULL));
1179 Result = LegalizeOp(Result);
1184 case ISD::ADD_PARTS:
1185 case ISD::SUB_PARTS:
1186 case ISD::SHL_PARTS:
1187 case ISD::SRA_PARTS:
1188 case ISD::SRL_PARTS: {
1189 std::vector<SDOperand> Ops;
1190 bool Changed = false;
1191 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1192 Ops.push_back(LegalizeOp(Node->getOperand(i)));
1193 Changed |= Ops.back() != Node->getOperand(i);
1196 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end());
1197 Result = DAG.getNode(Node->getOpcode(), VTs, Ops);
1200 // Since these produce multiple values, make sure to remember that we
1201 // legalized all of them.
1202 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1203 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
1204 return Result.getValue(Op.ResNo);
1221 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS
1222 switch (getTypeAction(Node->getOperand(1).getValueType())) {
1223 case Expand: assert(0 && "Not possible");
1225 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
1228 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the RHS.
1231 if (Tmp1 != Node->getOperand(0) ||
1232 Tmp2 != Node->getOperand(1))
1233 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
1238 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS
1239 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS
1240 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1241 case TargetLowering::Legal:
1242 if (Tmp1 != Node->getOperand(0) ||
1243 Tmp2 != Node->getOperand(1))
1244 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1247 case TargetLowering::Promote:
1248 case TargetLowering::Custom:
1249 assert(0 && "Cannot promote/custom handle this yet!");
1250 case TargetLowering::Expand: {
1251 MVT::ValueType VT = Node->getValueType(0);
1252 unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
1253 Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
1254 Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
1255 Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
1264 Tmp1 = LegalizeOp(Node->getOperand(0)); // Op
1265 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1266 case TargetLowering::Legal:
1267 if (Tmp1 != Node->getOperand(0))
1268 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1270 case TargetLowering::Promote: {
1271 MVT::ValueType OVT = Tmp1.getValueType();
1272 MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
1274 // Zero extend the argument.
1275 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
1276 // Perform the larger operation, then subtract if needed.
1277 Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1278 switch(Node->getOpcode())
1284 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
1285 Tmp2 = DAG.getSetCC(ISD::SETEQ, TLI.getSetCCResultTy(), Tmp1,
1286 DAG.getConstant(getSizeInBits(NVT), NVT));
1287 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
1288 DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
1291 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
1292 Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
1293 DAG.getConstant(getSizeInBits(NVT) -
1294 getSizeInBits(OVT), NVT));
1299 case TargetLowering::Custom:
1300 assert(0 && "Cannot custom handle this yet!");
1301 case TargetLowering::Expand:
1302 switch(Node->getOpcode())
1305 static const uint64_t mask[6] = {
1306 0x5555555555555555ULL, 0x3333333333333333ULL,
1307 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
1308 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
1310 MVT::ValueType VT = Tmp1.getValueType();
1311 MVT::ValueType ShVT = TLI.getShiftAmountTy();
1312 unsigned len = getSizeInBits(VT);
1313 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
1314 //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
1315 Tmp2 = DAG.getConstant(mask[i], VT);
1316 Tmp3 = DAG.getConstant(1ULL << i, ShVT);
1317 Tmp1 = DAG.getNode(ISD::ADD, VT,
1318 DAG.getNode(ISD::AND, VT, Tmp1, Tmp2),
1319 DAG.getNode(ISD::AND, VT,
1320 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3),
1327 /* for now, we do this:
1332 x = x | (x >>32); // for 64-bit input
1333 return popcount(~x);
1335 but see also: http://www.hackersdelight.org/HDcode/nlz.cc */
1336 MVT::ValueType VT = Tmp1.getValueType();
1337 MVT::ValueType ShVT = TLI.getShiftAmountTy();
1338 unsigned len = getSizeInBits(VT);
1339 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
1340 Tmp3 = DAG.getConstant(1ULL << i, ShVT);
1341 Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1,
1342 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3));
1344 Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT));
1345 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
1349 // for now, we use: { return popcount(~x & (x - 1)); }
1350 // unless the target has ctlz but not ctpop, in which case we use:
1351 // { return 32 - nlz(~x & (x-1)); }
1352 // see also http://www.hackersdelight.org/HDcode/ntz.cc
1353 MVT::ValueType VT = Tmp1.getValueType();
1354 Tmp2 = DAG.getConstant(~0ULL, VT);
1355 Tmp3 = DAG.getNode(ISD::AND, VT,
1356 DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2),
1357 DAG.getNode(ISD::SUB, VT, Tmp1,
1358 DAG.getConstant(1, VT)));
1359 // If ISD::CTLZ is legal and CTPOP isn't, then do that instead
1360 if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal &&
1361 TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) {
1362 Result = LegalizeOp(DAG.getNode(ISD::SUB, VT,
1363 DAG.getConstant(getSizeInBits(VT), VT),
1364 DAG.getNode(ISD::CTLZ, VT, Tmp3)));
1366 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
1371 assert(0 && "Cannot expand this yet!");
1384 Tmp1 = LegalizeOp(Node->getOperand(0));
1385 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
1386 case TargetLowering::Legal:
1387 if (Tmp1 != Node->getOperand(0))
1388 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1390 case TargetLowering::Promote:
1391 case TargetLowering::Custom:
1392 assert(0 && "Cannot promote/custom handle this yet!");
1393 case TargetLowering::Expand:
1394 switch(Node->getOpcode()) {
1396 // Expand Y = FNEG(X) -> Y = SUB -0.0, X
1397 Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
1398 Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0),
1403 // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
1404 MVT::ValueType VT = Node->getValueType(0);
1405 Tmp2 = DAG.getConstantFP(0.0, VT);
1406 Tmp2 = DAG.getSetCC(ISD::SETUGT, TLI.getSetCCResultTy(), Tmp1, Tmp2);
1407 Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
1408 Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
1409 Result = LegalizeOp(Result);
1415 MVT::ValueType VT = Node->getValueType(0);
1416 Type *T = VT == MVT::f32 ? Type::FloatTy : Type::DoubleTy;
1417 const char *FnName = 0;
1418 switch(Node->getOpcode()) {
1419 case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
1420 case ISD::FSIN: FnName = VT == MVT::f32 ? "sinf" : "sin"; break;
1421 case ISD::FCOS: FnName = VT == MVT::f32 ? "cosf" : "cos"; break;
1422 default: assert(0 && "Unreachable!");
1424 std::vector<std::pair<SDOperand, const Type*> > Args;
1425 Args.push_back(std::make_pair(Tmp1, T));
1426 // FIXME: should use ExpandLibCall!
1427 std::pair<SDOperand,SDOperand> CallResult =
1428 TLI.LowerCallTo(DAG.getEntryNode(), T, false, CallingConv::C, true,
1429 DAG.getExternalSymbol(FnName, VT), Args, DAG);
1430 Result = LegalizeOp(CallResult.first);
1434 assert(0 && "Unreachable!");
1440 // Conversion operators. The source and destination have different types.
1441 case ISD::ZERO_EXTEND:
1442 case ISD::SIGN_EXTEND:
1444 case ISD::FP_EXTEND:
1446 case ISD::FP_TO_SINT:
1447 case ISD::FP_TO_UINT:
1448 case ISD::SINT_TO_FP:
1449 case ISD::UINT_TO_FP:
1450 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1452 //still made need to expand if the op is illegal, but the types are legal
1453 if (Node->getOpcode() == ISD::UINT_TO_FP ||
1454 Node->getOpcode() == ISD::SINT_TO_FP) {
1455 bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
1456 switch (TLI.getOperationAction(Node->getOpcode(),
1457 Node->getOperand(0).getValueType())) {
1458 default: assert(0 && "Unknown operation action!");
1459 case TargetLowering::Expand:
1461 Result = ExpandLegalUINT_TO_FP(LegalizeOp(Node->getOperand(0)),
1462 Node->getValueType(0));
1464 assert(0 && "Legalize cannot Expand SINT_TO_FP yet");
1465 AddLegalizedOperand(Op, Result);
1467 case TargetLowering::Promote:
1468 Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)),
1469 Node->getValueType(0),
1471 AddLegalizedOperand(Op, Result);
1473 case TargetLowering::Legal:
1477 Tmp1 = LegalizeOp(Node->getOperand(0));
1478 if (Tmp1 != Node->getOperand(0))
1479 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
1482 if (Node->getOpcode() == ISD::SINT_TO_FP ||
1483 Node->getOpcode() == ISD::UINT_TO_FP) {
1484 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
1485 Node->getValueType(0), Node->getOperand(0));
1487 } else if (Node->getOpcode() == ISD::TRUNCATE) {
1488 // In the expand case, we must be dealing with a truncate, because
1489 // otherwise the result would be larger than the source.
1490 ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1492 // Since the result is legal, we should just be able to truncate the low
1493 // part of the source.
1494 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
1497 assert(0 && "Shouldn't need to expand other operators here!");
1500 switch (Node->getOpcode()) {
1501 case ISD::ZERO_EXTEND:
1502 Result = PromoteOp(Node->getOperand(0));
1503 // NOTE: Any extend would work here...
1504 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
1505 Result = DAG.getZeroExtendInReg(Result,
1506 Node->getOperand(0).getValueType());
1508 case ISD::SIGN_EXTEND:
1509 Result = PromoteOp(Node->getOperand(0));
1510 // NOTE: Any extend would work here...
1511 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
1512 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1514 DAG.getValueType(Node->getOperand(0).getValueType()));
1517 Result = PromoteOp(Node->getOperand(0));
1518 Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
1520 case ISD::FP_EXTEND:
1521 Result = PromoteOp(Node->getOperand(0));
1522 if (Result.getValueType() != Op.getValueType())
1523 // Dynamically dead while we have only 2 FP types.
1524 Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
1527 case ISD::FP_TO_SINT:
1528 case ISD::FP_TO_UINT:
1529 Result = PromoteOp(Node->getOperand(0));
1530 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
1532 case ISD::SINT_TO_FP:
1533 Result = PromoteOp(Node->getOperand(0));
1534 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1536 DAG.getValueType(Node->getOperand(0).getValueType()));
1537 Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result);
1539 case ISD::UINT_TO_FP:
1540 Result = PromoteOp(Node->getOperand(0));
1541 Result = DAG.getZeroExtendInReg(Result,
1542 Node->getOperand(0).getValueType());
1543 Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
1548 case ISD::FP_ROUND_INREG:
1549 case ISD::SIGN_EXTEND_INREG: {
1550 Tmp1 = LegalizeOp(Node->getOperand(0));
1551 MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
1553 // If this operation is not supported, convert it to a shl/shr or load/store
1555 switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
1556 default: assert(0 && "This action not supported for this op yet!");
1557 case TargetLowering::Legal:
1558 if (Tmp1 != Node->getOperand(0))
1559 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
1560 DAG.getValueType(ExtraVT));
1562 case TargetLowering::Expand:
1563 // If this is an integer extend and shifts are supported, do that.
1564 if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1565 // NOTE: we could fall back on load/store here too for targets without
1566 // SAR. However, it is doubtful that any exist.
1567 unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
1568 MVT::getSizeInBits(ExtraVT);
1569 SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
1570 Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
1571 Node->getOperand(0), ShiftCst);
1572 Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
1574 } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
1575 // The only way we can lower this is to turn it into a STORETRUNC,
1576 // EXTLOAD pair, targetting a temporary location (a stack slot).
1578 // NOTE: there is a choice here between constantly creating new stack
1579 // slots and always reusing the same one. We currently always create
1580 // new ones, as reuse may inhibit scheduling.
1581 const Type *Ty = MVT::getTypeForValueType(ExtraVT);
1582 unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
1583 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty);
1584 MachineFunction &MF = DAG.getMachineFunction();
1586 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
1587 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
1588 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
1589 Node->getOperand(0), StackSlot,
1590 DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT));
1591 Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
1592 Result, StackSlot, DAG.getSrcValue(NULL),
1595 assert(0 && "Unknown op");
1597 Result = LegalizeOp(Result);
1604 // Note that LegalizeOp may be reentered even from single-use nodes, which
1605 // means that we always must cache transformed nodes.
1606 AddLegalizedOperand(Op, Result);
1610 /// PromoteOp - Given an operation that produces a value in an invalid type,
1611 /// promote it to compute the value into a larger type. The produced value will
1612 /// have the correct bits for the low portion of the register, but no guarantee
1613 /// is made about the top bits: it may be zero, sign-extended, or garbage.
1614 SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
1615 MVT::ValueType VT = Op.getValueType();
1616 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1617 assert(getTypeAction(VT) == Promote &&
1618 "Caller should expand or legalize operands that are not promotable!");
1619 assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
1620 "Cannot promote to smaller type!");
1622 SDOperand Tmp1, Tmp2, Tmp3;
1625 SDNode *Node = Op.Val;
1627 if (!Node->hasOneUse()) {
1628 std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
1629 if (I != PromotedNodes.end()) return I->second;
1631 assert(!PromotedNodes.count(Op) && "Repromoted this node??");
1634 // Promotion needs an optimization step to clean up after it, and is not
1635 // careful to avoid operations the target does not support. Make sure that
1636 // all generated operations are legalized in the next iteration.
1637 NeedsAnotherIteration = true;
1639 switch (Node->getOpcode()) {
1641 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1642 assert(0 && "Do not know how to promote this operator!");
1645 Result = DAG.getNode(ISD::UNDEF, NVT);
1648 Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
1649 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
1651 case ISD::ConstantFP:
1652 Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
1653 assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
1655 case ISD::CopyFromReg:
1656 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT,
1657 Node->getOperand(0));
1658 // Remember that we legalized the chain.
1659 AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1663 assert(getTypeAction(TLI.getSetCCResultTy()) == Legal &&
1664 "SetCC type is not legal??");
1665 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
1666 TLI.getSetCCResultTy(), Node->getOperand(0),
1667 Node->getOperand(1));
1668 Result = LegalizeOp(Result);
1672 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1674 Result = LegalizeOp(Node->getOperand(0));
1675 assert(Result.getValueType() >= NVT &&
1676 "This truncation doesn't make sense!");
1677 if (Result.getValueType() > NVT) // Truncate to NVT instead of VT
1678 Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
1681 // The truncation is not required, because we don't guarantee anything
1682 // about high bits anyway.
1683 Result = PromoteOp(Node->getOperand(0));
1686 ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1687 // Truncate the low part of the expanded value to the result type
1688 Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1);
1691 case ISD::SIGN_EXTEND:
1692 case ISD::ZERO_EXTEND:
1693 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1694 case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
1696 // Input is legal? Just do extend all the way to the larger type.
1697 Result = LegalizeOp(Node->getOperand(0));
1698 Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1701 // Promote the reg if it's smaller.
1702 Result = PromoteOp(Node->getOperand(0));
1703 // The high bits are not guaranteed to be anything. Insert an extend.
1704 if (Node->getOpcode() == ISD::SIGN_EXTEND)
1705 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
1706 DAG.getValueType(Node->getOperand(0).getValueType()));
1708 Result = DAG.getZeroExtendInReg(Result,
1709 Node->getOperand(0).getValueType());
1714 case ISD::FP_EXTEND:
1715 assert(0 && "Case not implemented. Dynamically dead with 2 FP types!");
1717 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1718 case Expand: assert(0 && "BUG: Cannot expand FP regs!");
1719 case Promote: assert(0 && "Unreachable with 2 FP types!");
1721 // Input is legal? Do an FP_ROUND_INREG.
1722 Result = LegalizeOp(Node->getOperand(0));
1723 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
1724 DAG.getValueType(VT));
1729 case ISD::SINT_TO_FP:
1730 case ISD::UINT_TO_FP:
1731 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1733 Result = LegalizeOp(Node->getOperand(0));
1734 // No extra round required here.
1735 Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1739 Result = PromoteOp(Node->getOperand(0));
1740 if (Node->getOpcode() == ISD::SINT_TO_FP)
1741 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1743 DAG.getValueType(Node->getOperand(0).getValueType()));
1745 Result = DAG.getZeroExtendInReg(Result,
1746 Node->getOperand(0).getValueType());
1747 // No extra round required here.
1748 Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1751 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
1752 Node->getOperand(0));
1753 // Round if we cannot tolerate excess precision.
1754 if (NoExcessFPPrecision)
1755 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
1756 DAG.getValueType(VT));
1761 case ISD::FP_TO_SINT:
1762 case ISD::FP_TO_UINT:
1763 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1765 Tmp1 = LegalizeOp(Node->getOperand(0));
1768 // The input result is prerounded, so we don't have to do anything
1770 Tmp1 = PromoteOp(Node->getOperand(0));
1773 assert(0 && "not implemented");
1775 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1780 Tmp1 = PromoteOp(Node->getOperand(0));
1781 assert(Tmp1.getValueType() == NVT);
1782 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1783 // NOTE: we do not have to do any extra rounding here for
1784 // NoExcessFPPrecision, because we know the input will have the appropriate
1785 // precision, and these operations don't modify precision at all.
1791 Tmp1 = PromoteOp(Node->getOperand(0));
1792 assert(Tmp1.getValueType() == NVT);
1793 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1794 if(NoExcessFPPrecision)
1795 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
1796 DAG.getValueType(VT));
1805 // The input may have strange things in the top bits of the registers, but
1806 // these operations don't care. They may have wierd bits going out, but
1807 // that too is okay if they are integer operations.
1808 Tmp1 = PromoteOp(Node->getOperand(0));
1809 Tmp2 = PromoteOp(Node->getOperand(1));
1810 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
1811 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1813 // However, if this is a floating point operation, they will give excess
1814 // precision that we may not be able to tolerate. If we DO allow excess
1815 // precision, just leave it, otherwise excise it.
1816 // FIXME: Why would we need to round FP ops more than integer ones?
1817 // Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
1818 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1819 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
1820 DAG.getValueType(VT));
1825 // These operators require that their input be sign extended.
1826 Tmp1 = PromoteOp(Node->getOperand(0));
1827 Tmp2 = PromoteOp(Node->getOperand(1));
1828 if (MVT::isInteger(NVT)) {
1829 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
1830 DAG.getValueType(VT));
1831 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
1832 DAG.getValueType(VT));
1834 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1836 // Perform FP_ROUND: this is probably overly pessimistic.
1837 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1838 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
1839 DAG.getValueType(VT));
1844 // These operators require that their input be zero extended.
1845 Tmp1 = PromoteOp(Node->getOperand(0));
1846 Tmp2 = PromoteOp(Node->getOperand(1));
1847 assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
1848 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
1849 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
1850 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1854 Tmp1 = PromoteOp(Node->getOperand(0));
1855 Tmp2 = LegalizeOp(Node->getOperand(1));
1856 Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
1859 // The input value must be properly sign extended.
1860 Tmp1 = PromoteOp(Node->getOperand(0));
1861 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
1862 DAG.getValueType(VT));
1863 Tmp2 = LegalizeOp(Node->getOperand(1));
1864 Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
1867 // The input value must be properly zero extended.
1868 Tmp1 = PromoteOp(Node->getOperand(0));
1869 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
1870 Tmp2 = LegalizeOp(Node->getOperand(1));
1871 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
1874 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
1875 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer.
1876 // FIXME: When the DAG combiner exists, change this to use EXTLOAD!
1877 if (MVT::isInteger(NVT))
1878 Result = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2,
1879 Node->getOperand(2), VT);
1881 Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp1, Tmp2,
1882 Node->getOperand(2), VT);
1884 // Remember that we legalized the chain.
1885 AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1888 switch (getTypeAction(Node->getOperand(0).getValueType())) {
1889 case Expand: assert(0 && "It's impossible to expand bools");
1891 Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition.
1894 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
1897 Tmp2 = PromoteOp(Node->getOperand(1)); // Legalize the op0
1898 Tmp3 = PromoteOp(Node->getOperand(2)); // Legalize the op1
1899 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
1903 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
1904 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee.
1906 std::vector<SDOperand> Ops;
1907 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i)
1908 Ops.push_back(LegalizeOp(Node->getOperand(i)));
1910 assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1911 "Can only promote single result calls");
1912 std::vector<MVT::ValueType> RetTyVTs;
1913 RetTyVTs.reserve(2);
1914 RetTyVTs.push_back(NVT);
1915 RetTyVTs.push_back(MVT::Other);
1916 SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops,
1917 Node->getOpcode() == ISD::TAILCALL);
1918 Result = SDOperand(NC, 0);
1920 // Insert the new chain mapping.
1921 AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1927 Tmp1 = Node->getOperand(0);
1928 //Zero extend the argument
1929 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
1930 // Perform the larger operation, then subtract if needed.
1931 Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1932 switch(Node->getOpcode())
1938 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
1939 Tmp2 = DAG.getSetCC(ISD::SETEQ, MVT::i1, Tmp1,
1940 DAG.getConstant(getSizeInBits(NVT), NVT));
1941 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
1942 DAG.getConstant(getSizeInBits(VT),NVT), Tmp1);
1945 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
1946 Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
1947 DAG.getConstant(getSizeInBits(NVT) -
1948 getSizeInBits(VT), NVT));
1954 assert(Result.Val && "Didn't set a result!");
1955 AddPromotedOperand(Op, Result);
1959 /// ExpandAddSub - Find a clever way to expand this add operation into
1961 void SelectionDAGLegalize::
1962 ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
1963 SDOperand &Lo, SDOperand &Hi) {
1964 // Expand the subcomponents.
1965 SDOperand LHSL, LHSH, RHSL, RHSH;
1966 ExpandOp(LHS, LHSL, LHSH);
1967 ExpandOp(RHS, RHSL, RHSH);
1969 // FIXME: this should be moved to the dag combiner someday.
1970 assert(NodeOp == ISD::ADD_PARTS || NodeOp == ISD::SUB_PARTS);
1971 if (LHSL.getValueType() == MVT::i32) {
1973 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(LHSL))
1974 if (C->getValue() == 0)
1976 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHSL))
1977 if (C->getValue() == 0)
1980 // Turn this into an add/sub of the high part only.
1982 DAG.getNode(NodeOp == ISD::ADD_PARTS ? ISD::ADD : ISD::SUB,
1983 LowEl.getValueType(), LHSH, RHSH);
1990 std::vector<SDOperand> Ops;
1991 Ops.push_back(LHSL);
1992 Ops.push_back(LHSH);
1993 Ops.push_back(RHSL);
1994 Ops.push_back(RHSH);
1996 std::vector<MVT::ValueType> VTs(2, LHSL.getValueType());
1997 Lo = DAG.getNode(NodeOp, VTs, Ops);
1998 Hi = Lo.getValue(1);
2001 void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
2002 SDOperand Op, SDOperand Amt,
2003 SDOperand &Lo, SDOperand &Hi) {
2004 // Expand the subcomponents.
2005 SDOperand LHSL, LHSH;
2006 ExpandOp(Op, LHSL, LHSH);
2008 std::vector<SDOperand> Ops;
2009 Ops.push_back(LHSL);
2010 Ops.push_back(LHSH);
2012 std::vector<MVT::ValueType> VTs;
2013 VTs.push_back(LHSL.getValueType());
2014 VTs.push_back(LHSH.getValueType());
2015 VTs.push_back(Amt.getValueType());
2016 Lo = DAG.getNode(NodeOp, VTs, Ops);
2017 Hi = Lo.getValue(1);
2021 /// ExpandShift - Try to find a clever way to expand this shift operation out to
2022 /// smaller elements. If we can't find a way that is more efficient than a
2023 /// libcall on this target, return false. Otherwise, return true with the
2024 /// low-parts expanded into Lo and Hi.
2025 bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
2026 SDOperand &Lo, SDOperand &Hi) {
2027 assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
2028 "This is not a shift!");
2030 MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
2031 SDOperand ShAmt = LegalizeOp(Amt);
2032 MVT::ValueType ShTy = ShAmt.getValueType();
2033 unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
2034 unsigned NVTBits = MVT::getSizeInBits(NVT);
2036 // Handle the case when Amt is an immediate. Other cases are currently broken
2037 // and are disabled.
2038 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
2039 unsigned Cst = CN->getValue();
2040 // Expand the incoming operand to be shifted, so that we have its parts
2042 ExpandOp(Op, InL, InH);
2046 Lo = DAG.getConstant(0, NVT);
2047 Hi = DAG.getConstant(0, NVT);
2048 } else if (Cst > NVTBits) {
2049 Lo = DAG.getConstant(0, NVT);
2050 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
2051 } else if (Cst == NVTBits) {
2052 Lo = DAG.getConstant(0, NVT);
2055 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
2056 Hi = DAG.getNode(ISD::OR, NVT,
2057 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
2058 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
2063 Lo = DAG.getConstant(0, NVT);
2064 Hi = DAG.getConstant(0, NVT);
2065 } else if (Cst > NVTBits) {
2066 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
2067 Hi = DAG.getConstant(0, NVT);
2068 } else if (Cst == NVTBits) {
2070 Hi = DAG.getConstant(0, NVT);
2072 Lo = DAG.getNode(ISD::OR, NVT,
2073 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
2074 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
2075 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
2080 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
2081 DAG.getConstant(NVTBits-1, ShTy));
2082 } else if (Cst > NVTBits) {
2083 Lo = DAG.getNode(ISD::SRA, NVT, InH,
2084 DAG.getConstant(Cst-NVTBits, ShTy));
2085 Hi = DAG.getNode(ISD::SRA, NVT, InH,
2086 DAG.getConstant(NVTBits-1, ShTy));
2087 } else if (Cst == NVTBits) {
2089 Hi = DAG.getNode(ISD::SRA, NVT, InH,
2090 DAG.getConstant(NVTBits-1, ShTy));
2092 Lo = DAG.getNode(ISD::OR, NVT,
2093 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
2094 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
2095 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
2100 // FIXME: The following code for expanding shifts using ISD::SELECT is buggy,
2101 // so disable it for now. Currently targets are handling this via SHL_PARTS
2105 // If we have an efficient select operation (or if the selects will all fold
2106 // away), lower to some complex code, otherwise just emit the libcall.
2107 if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal &&
2108 !isa<ConstantSDNode>(Amt))
2112 ExpandOp(Op, InL, InH);
2113 SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy, // NAmt = 32-ShAmt
2114 DAG.getConstant(NVTBits, ShTy), ShAmt);
2116 // Compare the unmasked shift amount against 32.
2117 SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), ShAmt,
2118 DAG.getConstant(NVTBits, ShTy));
2120 if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) {
2121 ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt, // ShAmt &= 31
2122 DAG.getConstant(NVTBits-1, ShTy));
2123 NAmt = DAG.getNode(ISD::AND, ShTy, NAmt, // NAmt &= 31
2124 DAG.getConstant(NVTBits-1, ShTy));
2127 if (Opc == ISD::SHL) {
2128 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt)
2129 DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
2130 DAG.getNode(ISD::SRL, NVT, InL, NAmt));
2131 SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31
2133 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
2134 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
2136 SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT,
2137 DAG.getSetCC(ISD::SETEQ,
2138 TLI.getSetCCResultTy(), NAmt,
2139 DAG.getConstant(32, ShTy)),
2140 DAG.getConstant(0, NVT),
2141 DAG.getNode(ISD::SHL, NVT, InH, NAmt));
2142 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt)
2144 DAG.getNode(ISD::SRL, NVT, InL, ShAmt));
2145 SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt); // T2 = InH >> ShAmt&31
2148 if (Opc == ISD::SRA)
2149 HiPart = DAG.getNode(ISD::SRA, NVT, InH,
2150 DAG.getConstant(NVTBits-1, ShTy));
2152 HiPart = DAG.getConstant(0, NVT);
2153 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
2154 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2);
2159 /// FindLatestCallSeqStart - Scan up the dag to find the latest (highest
2160 /// NodeDepth) node that is an CallSeqStart operation and occurs later than
2162 static void FindLatestCallSeqStart(SDNode *Node, SDNode *&Found) {
2163 if (Node->getNodeDepth() <= Found->getNodeDepth()) return;
2165 // If we found an CALLSEQ_START, we already know this node occurs later
2166 // than the Found node. Just remember this node and return.
2167 if (Node->getOpcode() == ISD::CALLSEQ_START) {
2172 // Otherwise, scan the operands of Node to see if any of them is a call.
2173 assert(Node->getNumOperands() != 0 &&
2174 "All leaves should have depth equal to the entry node!");
2175 for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i)
2176 FindLatestCallSeqStart(Node->getOperand(i).Val, Found);
2178 // Tail recurse for the last iteration.
2179 FindLatestCallSeqStart(Node->getOperand(Node->getNumOperands()-1).Val,
2184 /// FindEarliestCallSeqEnd - Scan down the dag to find the earliest (lowest
2185 /// NodeDepth) node that is an CallSeqEnd operation and occurs more recent
2187 static void FindEarliestCallSeqEnd(SDNode *Node, SDNode *&Found) {
2188 if (Found && Node->getNodeDepth() >= Found->getNodeDepth()) return;
2190 // If we found an CALLSEQ_END, we already know this node occurs earlier
2191 // than the Found node. Just remember this node and return.
2192 if (Node->getOpcode() == ISD::CALLSEQ_END) {
2197 // Otherwise, scan the operands of Node to see if any of them is a call.
2198 SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
2199 if (UI == E) return;
2200 for (--E; UI != E; ++UI)
2201 FindEarliestCallSeqEnd(*UI, Found);
2203 // Tail recurse for the last iteration.
2204 FindEarliestCallSeqEnd(*UI, Found);
2207 /// FindCallSeqEnd - Given a chained node that is part of a call sequence,
2208 /// find the CALLSEQ_END node that terminates the call sequence.
2209 static SDNode *FindCallSeqEnd(SDNode *Node) {
2210 if (Node->getOpcode() == ISD::CALLSEQ_END)
2212 if (Node->use_empty())
2213 return 0; // No CallSeqEnd
2215 if (Node->hasOneUse()) // Simple case, only has one user to check.
2216 return FindCallSeqEnd(*Node->use_begin());
2218 SDOperand TheChain(Node, Node->getNumValues()-1);
2219 if (TheChain.getValueType() != MVT::Other)
2220 TheChain = SDOperand(Node, 0);
2221 assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!");
2223 for (SDNode::use_iterator UI = Node->use_begin(),
2224 E = Node->use_end(); ; ++UI) {
2225 assert(UI != E && "Didn't find a user of the tokchain, no CALLSEQ_END!");
2227 // Make sure to only follow users of our token chain.
2229 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
2230 if (User->getOperand(i) == TheChain)
2231 if (SDNode *Result = FindCallSeqEnd(User))
2234 assert(0 && "Unreachable");
2238 /// FindCallSeqStart - Given a chained node that is part of a call sequence,
2239 /// find the CALLSEQ_START node that initiates the call sequence.
2240 static SDNode *FindCallSeqStart(SDNode *Node) {
2241 assert(Node && "Didn't find callseq_start for a call??");
2242 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
2244 assert(Node->getOperand(0).getValueType() == MVT::Other &&
2245 "Node doesn't have a token chain argument!");
2246 return FindCallSeqStart(Node->getOperand(0).Val);
2250 /// FindInputOutputChains - If we are replacing an operation with a call we need
2251 /// to find the call that occurs before and the call that occurs after it to
2252 /// properly serialize the calls in the block. The returned operand is the
2253 /// input chain value for the new call (e.g. the entry node or the previous
2254 /// call), and OutChain is set to be the chain node to update to point to the
2255 /// end of the call chain.
2256 static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain,
2258 SDNode *LatestCallSeqStart = Entry.Val;
2259 SDNode *LatestCallSeqEnd = 0;
2260 FindLatestCallSeqStart(OpNode, LatestCallSeqStart);
2261 //std::cerr<<"Found node: "; LatestCallSeqStart->dump(); std::cerr <<"\n";
2263 // It is possible that no ISD::CALLSEQ_START was found because there is no
2264 // previous call in the function. LatestCallStackDown may in that case be
2265 // the entry node itself. Do not attempt to find a matching CALLSEQ_END
2266 // unless LatestCallStackDown is an CALLSEQ_START.
2267 if (LatestCallSeqStart->getOpcode() == ISD::CALLSEQ_START)
2268 LatestCallSeqEnd = FindCallSeqEnd(LatestCallSeqStart);
2270 LatestCallSeqEnd = Entry.Val;
2271 assert(LatestCallSeqEnd && "NULL return from FindCallSeqEnd");
2273 // Finally, find the first call that this must come before, first we find the
2274 // CallSeqEnd that ends the call.
2276 FindEarliestCallSeqEnd(OpNode, OutChain);
2278 // If we found one, translate from the adj up to the callseq_start.
2280 OutChain = FindCallSeqStart(OutChain);
2282 return SDOperand(LatestCallSeqEnd, 0);
2285 /// SpliceCallInto - Given the result chain of a libcall (CallResult), and a
2286 void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult,
2288 // Nothing to splice it into?
2289 if (OutChain == 0) return;
2291 assert(OutChain->getOperand(0).getValueType() == MVT::Other);
2294 // Form a token factor node merging the old inval and the new inval.
2295 SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult,
2296 OutChain->getOperand(0));
2297 // Change the node to refer to the new token.
2298 OutChain->setAdjCallChain(InToken);
2302 // ExpandLibCall - Expand a node into a call to a libcall. If the result value
2303 // does not fit into a register, return the lo part and set the hi part to the
2304 // by-reg argument. If it does fit into a single register, return the result
2305 // and leave the Hi part unset.
2306 SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
2309 SDOperand InChain = FindInputOutputChains(Node, OutChain,
2310 DAG.getEntryNode());
2311 if (InChain.Val == 0)
2312 InChain = DAG.getEntryNode();
2314 TargetLowering::ArgListTy Args;
2315 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
2316 MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
2317 const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
2318 Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
2320 SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
2322 // Splice the libcall in wherever FindInputOutputChains tells us to.
2323 const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
2324 std::pair<SDOperand,SDOperand> CallInfo =
2325 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false,
2327 SpliceCallInto(CallInfo.second, OutChain);
2329 NeedsAnotherIteration = true;
2331 switch (getTypeAction(CallInfo.first.getValueType())) {
2332 default: assert(0 && "Unknown thing");
2334 return CallInfo.first;
2336 assert(0 && "Cannot promote this yet!");
2339 ExpandOp(CallInfo.first, Lo, Hi);
2345 /// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
2346 /// destination type is legal.
2347 SDOperand SelectionDAGLegalize::
2348 ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
2349 assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!");
2350 assert(getTypeAction(Source.getValueType()) == Expand &&
2351 "This is not an expansion!");
2352 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
2355 assert(Source.getValueType() == MVT::i64 &&
2356 "This only works for 64-bit -> FP");
2357 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
2358 // incoming integer is set. To handle this, we dynamically test to see if
2359 // it is set, and, if so, add a fudge factor.
2361 ExpandOp(Source, Lo, Hi);
2363 // If this is unsigned, and not supported, first perform the conversion to
2364 // signed, then adjust the result if the sign bit is set.
2365 SDOperand SignedConv = ExpandIntToFP(true, DestTy,
2366 DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
2368 SDOperand SignSet = DAG.getSetCC(ISD::SETLT, TLI.getSetCCResultTy(), Hi,
2369 DAG.getConstant(0, Hi.getValueType()));
2370 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
2371 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
2372 SignSet, Four, Zero);
2373 uint64_t FF = 0x5f800000ULL;
2374 if (TLI.isLittleEndian()) FF <<= 32;
2375 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
2377 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
2378 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor),
2379 TLI.getPointerTy());
2380 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
2381 SDOperand FudgeInReg;
2382 if (DestTy == MVT::f32)
2383 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
2384 DAG.getSrcValue(NULL));
2386 assert(DestTy == MVT::f64 && "Unexpected conversion");
2387 FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
2388 CPIdx, DAG.getSrcValue(NULL), MVT::f32);
2390 return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg);
2393 // Check to see if the target has a custom way to lower this. If so, use it.
2394 switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
2395 default: assert(0 && "This action not implemented for this operation!");
2396 case TargetLowering::Legal:
2397 case TargetLowering::Expand:
2398 break; // This case is handled below.
2399 case TargetLowering::Custom:
2400 Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
2401 return LegalizeOp(TLI.LowerOperation(Source, DAG));
2404 // Expand the source, then glue it back together for the call. We must expand
2405 // the source in case it is shared (this pass of legalize must traverse it).
2406 SDOperand SrcLo, SrcHi;
2407 ExpandOp(Source, SrcLo, SrcHi);
2408 Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
2410 SDNode *OutChain = 0;
2411 SDOperand InChain = FindInputOutputChains(Source.Val, OutChain,
2412 DAG.getEntryNode());
2413 const char *FnName = 0;
2414 if (DestTy == MVT::f32)
2415 FnName = "__floatdisf";
2417 assert(DestTy == MVT::f64 && "Unknown fp value type!");
2418 FnName = "__floatdidf";
2421 SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy());
2423 TargetLowering::ArgListTy Args;
2424 const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType());
2426 Args.push_back(std::make_pair(Source, ArgTy));
2428 // We don't care about token chains for libcalls. We just use the entry
2429 // node as our input and ignore the output chain. This allows us to place
2430 // calls wherever we need them to satisfy data dependences.
2431 const Type *RetTy = MVT::getTypeForValueType(DestTy);
2433 std::pair<SDOperand,SDOperand> CallResult =
2434 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, true,
2437 SpliceCallInto(CallResult.second, OutChain);
2438 return CallResult.first;
2443 /// ExpandOp - Expand the specified SDOperand into its two component pieces
2444 /// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the
2445 /// LegalizeNodes map is filled in for any results that are not expanded, the
2446 /// ExpandedNodes map is filled in for any results that are expanded, and the
2447 /// Lo/Hi values are returned.
2448 void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
2449 MVT::ValueType VT = Op.getValueType();
2450 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
2451 SDNode *Node = Op.Val;
2452 assert(getTypeAction(VT) == Expand && "Not an expanded type!");
2453 assert(MVT::isInteger(VT) && "Cannot expand FP values!");
2454 assert(MVT::isInteger(NVT) && NVT < VT &&
2455 "Cannot expand to FP value or to larger int value!");
2457 // If there is more than one use of this, see if we already expanded it.
2458 // There is no use remembering values that only have a single use, as the map
2459 // entries will never be reused.
2460 if (!Node->hasOneUse()) {
2461 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
2462 = ExpandedNodes.find(Op);
2463 if (I != ExpandedNodes.end()) {
2464 Lo = I->second.first;
2465 Hi = I->second.second;
2469 assert(!ExpandedNodes.count(Op) && "Re-expanding a node!");
2472 // Expanding to multiple registers needs to perform an optimization step, and
2473 // is not careful to avoid operations the target does not support. Make sure
2474 // that all generated operations are legalized in the next iteration.
2475 NeedsAnotherIteration = true;
2477 switch (Node->getOpcode()) {
2479 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
2480 assert(0 && "Do not know how to expand this operator!");
2483 Lo = DAG.getNode(ISD::UNDEF, NVT);
2484 Hi = DAG.getNode(ISD::UNDEF, NVT);
2486 case ISD::Constant: {
2487 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
2488 Lo = DAG.getConstant(Cst, NVT);
2489 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
2493 case ISD::CopyFromReg: {
2494 unsigned Reg = cast<RegSDNode>(Node)->getReg();
2495 // Aggregate register values are always in consequtive pairs.
2496 Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
2497 Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
2499 // Remember that we legalized the chain.
2500 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
2502 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
2506 case ISD::BUILD_PAIR:
2507 // Legalize both operands. FIXME: in the future we should handle the case
2508 // where the two elements are not legal.
2509 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
2510 Lo = LegalizeOp(Node->getOperand(0));
2511 Hi = LegalizeOp(Node->getOperand(1));
2515 ExpandOp(Node->getOperand(0), Lo, Hi);
2516 Lo = DAG.getNode(ISD::ADD, NVT, // ctpop(HL) -> ctpop(H)+ctpop(L)
2517 DAG.getNode(ISD::CTPOP, NVT, Lo),
2518 DAG.getNode(ISD::CTPOP, NVT, Hi));
2519 Hi = DAG.getConstant(0, NVT);
2523 // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
2524 ExpandOp(Node->getOperand(0), Lo, Hi);
2525 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
2526 SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
2527 SDOperand TopNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(),
2529 SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
2530 LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
2532 Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
2533 Hi = DAG.getConstant(0, NVT);
2538 // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
2539 ExpandOp(Node->getOperand(0), Lo, Hi);
2540 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
2541 SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
2542 SDOperand BotNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(),
2544 SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
2545 HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
2547 Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
2548 Hi = DAG.getConstant(0, NVT);
2553 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
2554 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer.
2555 Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
2557 // Increment the pointer to the other half.
2558 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
2559 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
2560 getIntPtrConstant(IncrementSize));
2561 //Is this safe? declaring that the two parts of the split load
2562 //are from the same instruction?
2563 Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
2565 // Build a factor node to remember that this load is independent of the
2567 SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
2570 // Remember that we legalized the chain.
2571 AddLegalizedOperand(Op.getValue(1), TF);
2572 if (!TLI.isLittleEndian())
2578 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain.
2579 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee.
2581 bool Changed = false;
2582 std::vector<SDOperand> Ops;
2583 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
2584 Ops.push_back(LegalizeOp(Node->getOperand(i)));
2585 Changed |= Ops.back() != Node->getOperand(i);
2588 assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
2589 "Can only expand a call once so far, not i64 -> i16!");
2591 std::vector<MVT::ValueType> RetTyVTs;
2592 RetTyVTs.reserve(3);
2593 RetTyVTs.push_back(NVT);
2594 RetTyVTs.push_back(NVT);
2595 RetTyVTs.push_back(MVT::Other);
2596 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops,
2597 Node->getOpcode() == ISD::TAILCALL);
2598 Lo = SDOperand(NC, 0);
2599 Hi = SDOperand(NC, 1);
2601 // Insert the new chain mapping.
2602 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
2607 case ISD::XOR: { // Simple logical operators -> two trivial pieces.
2608 SDOperand LL, LH, RL, RH;
2609 ExpandOp(Node->getOperand(0), LL, LH);
2610 ExpandOp(Node->getOperand(1), RL, RH);
2611 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
2612 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
2616 SDOperand C, LL, LH, RL, RH;
2618 switch (getTypeAction(Node->getOperand(0).getValueType())) {
2619 case Expand: assert(0 && "It's impossible to expand bools");
2621 C = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
2624 C = PromoteOp(Node->getOperand(0)); // Promote the condition.
2627 ExpandOp(Node->getOperand(1), LL, LH);
2628 ExpandOp(Node->getOperand(2), RL, RH);
2629 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
2630 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
2633 case ISD::SIGN_EXTEND: {
2635 switch (getTypeAction(Node->getOperand(0).getValueType())) {
2636 case Expand: assert(0 && "expand-expand not implemented yet!");
2637 case Legal: In = LegalizeOp(Node->getOperand(0)); break;
2639 In = PromoteOp(Node->getOperand(0));
2640 // Emit the appropriate sign_extend_inreg to get the value we want.
2641 In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In,
2642 DAG.getValueType(Node->getOperand(0).getValueType()));
2646 // The low part is just a sign extension of the input (which degenerates to
2648 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In);
2650 // The high part is obtained by SRA'ing all but one of the bits of the lo
2652 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
2653 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1,
2654 TLI.getShiftAmountTy()));
2657 case ISD::ZERO_EXTEND: {
2659 switch (getTypeAction(Node->getOperand(0).getValueType())) {
2660 case Expand: assert(0 && "expand-expand not implemented yet!");
2661 case Legal: In = LegalizeOp(Node->getOperand(0)); break;
2663 In = PromoteOp(Node->getOperand(0));
2664 // Emit the appropriate zero_extend_inreg to get the value we want.
2665 In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType());
2669 // The low part is just a zero extension of the input (which degenerates to
2671 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In);
2673 // The high part is just a zero.
2674 Hi = DAG.getConstant(0, NVT);
2677 // These operators cannot be expanded directly, emit them as calls to
2678 // library functions.
2679 case ISD::FP_TO_SINT:
2680 if (Node->getOperand(0).getValueType() == MVT::f32)
2681 Lo = ExpandLibCall("__fixsfdi", Node, Hi);
2683 Lo = ExpandLibCall("__fixdfdi", Node, Hi);
2685 case ISD::FP_TO_UINT:
2686 if (Node->getOperand(0).getValueType() == MVT::f32)
2687 Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
2689 Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
2693 // If we can emit an efficient shift operation, do so now.
2694 if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
2697 // If this target supports SHL_PARTS, use it.
2698 if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) {
2699 ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1),
2704 // Otherwise, emit a libcall.
2705 Lo = ExpandLibCall("__ashldi3", Node, Hi);
2709 // If we can emit an efficient shift operation, do so now.
2710 if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
2713 // If this target supports SRA_PARTS, use it.
2714 if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) {
2715 ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1),
2720 // Otherwise, emit a libcall.
2721 Lo = ExpandLibCall("__ashrdi3", Node, Hi);
2724 // If we can emit an efficient shift operation, do so now.
2725 if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
2728 // If this target supports SRL_PARTS, use it.
2729 if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) {
2730 ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1),
2735 // Otherwise, emit a libcall.
2736 Lo = ExpandLibCall("__lshrdi3", Node, Hi);
2740 ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1),
2744 ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1),
2748 if (TLI.getOperationAction(ISD::MULHU, NVT) == TargetLowering::Legal) {
2749 SDOperand LL, LH, RL, RH;
2750 ExpandOp(Node->getOperand(0), LL, LH);
2751 ExpandOp(Node->getOperand(1), RL, RH);
2752 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
2753 RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
2754 LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
2755 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
2756 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
2757 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
2759 Lo = ExpandLibCall("__muldi3" , Node, Hi); break;
2763 case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
2764 case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
2765 case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
2766 case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
2769 // Remember in a map if the values will be reused later.
2770 if (!Node->hasOneUse()) {
2771 bool isNew = ExpandedNodes.insert(std::make_pair(Op,
2772 std::make_pair(Lo, Hi))).second;
2773 assert(isNew && "Value already expanded?!?");
2778 // SelectionDAG::Legalize - This is the entry point for the file.
2780 void SelectionDAG::Legalize() {
2781 /// run - This is the main entry point to this class.
2783 SelectionDAGLegalize(*this).Run();