1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeOrdering.h"
16 #include "SDNodeDbgValue.h"
17 #include "llvm/CallingConv.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DebugInfo.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Function.h"
22 #include "llvm/GlobalAlias.h"
23 #include "llvm/GlobalVariable.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Assembly/Writer.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
28 #include "llvm/CodeGen/MachineConstantPool.h"
29 #include "llvm/CodeGen/MachineFrameInfo.h"
30 #include "llvm/CodeGen/MachineModuleInfo.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include "llvm/Target/TargetData.h"
33 #include "llvm/Target/TargetLowering.h"
34 #include "llvm/Target/TargetSelectionDAGInfo.h"
35 #include "llvm/Target/TargetOptions.h"
36 #include "llvm/Target/TargetInstrInfo.h"
37 #include "llvm/Target/TargetIntrinsicInfo.h"
38 #include "llvm/Target/TargetMachine.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/ManagedStatic.h"
43 #include "llvm/Support/MathExtras.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Support/Mutex.h"
46 #include "llvm/ADT/SetVector.h"
47 #include "llvm/ADT/SmallPtrSet.h"
48 #include "llvm/ADT/SmallSet.h"
49 #include "llvm/ADT/SmallVector.h"
50 #include "llvm/ADT/StringExtras.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 static const fltSemantics *EVTToAPFloatSemantics(EVT VT) {
63 switch (VT.getSimpleVT().SimpleTy) {
64 default: llvm_unreachable("Unknown FP format");
65 case MVT::f16: return &APFloat::IEEEhalf;
66 case MVT::f32: return &APFloat::IEEEsingle;
67 case MVT::f64: return &APFloat::IEEEdouble;
68 case MVT::f80: return &APFloat::x87DoubleExtended;
69 case MVT::f128: return &APFloat::IEEEquad;
70 case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
74 // Default null implementations of the callbacks.
75 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
76 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
78 //===----------------------------------------------------------------------===//
79 // ConstantFPSDNode Class
80 //===----------------------------------------------------------------------===//
82 /// isExactlyValue - We don't rely on operator== working on double values, as
83 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
84 /// As such, this method can be used to do an exact bit-for-bit comparison of
85 /// two floating point values.
86 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
87 return getValueAPF().bitwiseIsEqual(V);
90 bool ConstantFPSDNode::isValueValidForType(EVT VT,
92 assert(VT.isFloatingPoint() && "Can only convert between FP types");
94 // PPC long double cannot be converted to any other type.
95 if (VT == MVT::ppcf128 ||
96 &Val.getSemantics() == &APFloat::PPCDoubleDouble)
99 // convert modifies in place, so make a copy.
100 APFloat Val2 = APFloat(Val);
102 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven,
107 //===----------------------------------------------------------------------===//
109 //===----------------------------------------------------------------------===//
111 /// isBuildVectorAllOnes - Return true if the specified node is a
112 /// BUILD_VECTOR where all of the elements are ~0 or undef.
113 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
114 // Look through a bit convert.
115 if (N->getOpcode() == ISD::BITCAST)
116 N = N->getOperand(0).getNode();
118 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
120 unsigned i = 0, e = N->getNumOperands();
122 // Skip over all of the undef values.
123 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
126 // Do not accept an all-undef vector.
127 if (i == e) return false;
129 // Do not accept build_vectors that aren't all constants or which have non-~0
130 // elements. We have to be a bit careful here, as the type of the constant
131 // may not be the same as the type of the vector elements due to type
132 // legalization (the elements are promoted to a legal type for the target and
133 // a vector of a type may be legal when the base element type is not).
134 // We only want to check enough bits to cover the vector elements, because
135 // we care if the resultant vector is all ones, not whether the individual
137 SDValue NotZero = N->getOperand(i);
138 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
139 if (isa<ConstantSDNode>(NotZero)) {
140 if (cast<ConstantSDNode>(NotZero)->getAPIntValue().countTrailingOnes() <
143 } else if (isa<ConstantFPSDNode>(NotZero)) {
144 if (cast<ConstantFPSDNode>(NotZero)->getValueAPF()
145 .bitcastToAPInt().countTrailingOnes() < EltSize)
150 // Okay, we have at least one ~0 value, check to see if the rest match or are
151 // undefs. Even with the above element type twiddling, this should be OK, as
152 // the same type legalization should have applied to all the elements.
153 for (++i; i != e; ++i)
154 if (N->getOperand(i) != NotZero &&
155 N->getOperand(i).getOpcode() != ISD::UNDEF)
161 /// isBuildVectorAllZeros - Return true if the specified node is a
162 /// BUILD_VECTOR where all of the elements are 0 or undef.
163 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
164 // Look through a bit convert.
165 if (N->getOpcode() == ISD::BITCAST)
166 N = N->getOperand(0).getNode();
168 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
170 unsigned i = 0, e = N->getNumOperands();
172 // Skip over all of the undef values.
173 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
176 // Do not accept an all-undef vector.
177 if (i == e) return false;
179 // Do not accept build_vectors that aren't all constants or which have non-0
181 SDValue Zero = N->getOperand(i);
182 if (isa<ConstantSDNode>(Zero)) {
183 if (!cast<ConstantSDNode>(Zero)->isNullValue())
185 } else if (isa<ConstantFPSDNode>(Zero)) {
186 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
191 // Okay, we have at least one 0 value, check to see if the rest match or are
193 for (++i; i != e; ++i)
194 if (N->getOperand(i) != Zero &&
195 N->getOperand(i).getOpcode() != ISD::UNDEF)
200 /// isScalarToVector - Return true if the specified node is a
201 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
202 /// element is not an undef.
203 bool ISD::isScalarToVector(const SDNode *N) {
204 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
207 if (N->getOpcode() != ISD::BUILD_VECTOR)
209 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
211 unsigned NumElems = N->getNumOperands();
214 for (unsigned i = 1; i < NumElems; ++i) {
215 SDValue V = N->getOperand(i);
216 if (V.getOpcode() != ISD::UNDEF)
222 /// allOperandsUndef - Return true if the node has at least one operand
223 /// and all operands of the specified node are ISD::UNDEF.
224 bool ISD::allOperandsUndef(const SDNode *N) {
225 // Return false if the node has no operands.
226 // This is "logically inconsistent" with the definition of "all" but
227 // is probably the desired behavior.
228 if (N->getNumOperands() == 0)
231 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
232 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
238 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
239 /// when given the operation for (X op Y).
240 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
241 // To perform this operation, we just need to swap the L and G bits of the
243 unsigned OldL = (Operation >> 2) & 1;
244 unsigned OldG = (Operation >> 1) & 1;
245 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
246 (OldL << 1) | // New G bit
247 (OldG << 2)); // New L bit.
250 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
251 /// 'op' is a valid SetCC operation.
252 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
253 unsigned Operation = Op;
255 Operation ^= 7; // Flip L, G, E bits, but not U.
257 Operation ^= 15; // Flip all of the condition bits.
259 if (Operation > ISD::SETTRUE2)
260 Operation &= ~8; // Don't let N and U bits get set.
262 return ISD::CondCode(Operation);
266 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
267 /// signed operation and 2 if the result is an unsigned comparison. Return zero
268 /// if the operation does not depend on the sign of the input (setne and seteq).
269 static int isSignedOp(ISD::CondCode Opcode) {
271 default: llvm_unreachable("Illegal integer setcc operation!");
273 case ISD::SETNE: return 0;
277 case ISD::SETGE: return 1;
281 case ISD::SETUGE: return 2;
285 /// getSetCCOrOperation - Return the result of a logical OR between different
286 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
287 /// returns SETCC_INVALID if it is not possible to represent the resultant
289 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
291 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
292 // Cannot fold a signed integer setcc with an unsigned integer setcc.
293 return ISD::SETCC_INVALID;
295 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
297 // If the N and U bits get set then the resultant comparison DOES suddenly
298 // care about orderedness, and is true when ordered.
299 if (Op > ISD::SETTRUE2)
300 Op &= ~16; // Clear the U bit if the N bit is set.
302 // Canonicalize illegal integer setcc's.
303 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
306 return ISD::CondCode(Op);
309 /// getSetCCAndOperation - Return the result of a logical AND between different
310 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
311 /// function returns zero if it is not possible to represent the resultant
313 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
315 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
316 // Cannot fold a signed setcc with an unsigned setcc.
317 return ISD::SETCC_INVALID;
319 // Combine all of the condition bits.
320 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
322 // Canonicalize illegal integer setcc's.
326 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
327 case ISD::SETOEQ: // SETEQ & SETU[LG]E
328 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
329 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
330 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
337 //===----------------------------------------------------------------------===//
338 // SDNode Profile Support
339 //===----------------------------------------------------------------------===//
341 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
343 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
347 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
348 /// solely with their pointer.
349 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
350 ID.AddPointer(VTList.VTs);
353 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
355 static void AddNodeIDOperands(FoldingSetNodeID &ID,
356 const SDValue *Ops, unsigned NumOps) {
357 for (; NumOps; --NumOps, ++Ops) {
358 ID.AddPointer(Ops->getNode());
359 ID.AddInteger(Ops->getResNo());
363 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
365 static void AddNodeIDOperands(FoldingSetNodeID &ID,
366 const SDUse *Ops, unsigned NumOps) {
367 for (; NumOps; --NumOps, ++Ops) {
368 ID.AddPointer(Ops->getNode());
369 ID.AddInteger(Ops->getResNo());
373 static void AddNodeIDNode(FoldingSetNodeID &ID,
374 unsigned short OpC, SDVTList VTList,
375 const SDValue *OpList, unsigned N) {
376 AddNodeIDOpcode(ID, OpC);
377 AddNodeIDValueTypes(ID, VTList);
378 AddNodeIDOperands(ID, OpList, N);
381 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
383 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
384 switch (N->getOpcode()) {
385 case ISD::TargetExternalSymbol:
386 case ISD::ExternalSymbol:
387 llvm_unreachable("Should only be used on nodes with operands");
388 default: break; // Normal nodes don't need extra info.
389 case ISD::TargetConstant:
391 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
393 case ISD::TargetConstantFP:
394 case ISD::ConstantFP: {
395 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
398 case ISD::TargetGlobalAddress:
399 case ISD::GlobalAddress:
400 case ISD::TargetGlobalTLSAddress:
401 case ISD::GlobalTLSAddress: {
402 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
403 ID.AddPointer(GA->getGlobal());
404 ID.AddInteger(GA->getOffset());
405 ID.AddInteger(GA->getTargetFlags());
408 case ISD::BasicBlock:
409 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
412 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
414 case ISD::RegisterMask:
415 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
418 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
420 case ISD::FrameIndex:
421 case ISD::TargetFrameIndex:
422 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
425 case ISD::TargetJumpTable:
426 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
427 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
429 case ISD::ConstantPool:
430 case ISD::TargetConstantPool: {
431 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
432 ID.AddInteger(CP->getAlignment());
433 ID.AddInteger(CP->getOffset());
434 if (CP->isMachineConstantPoolEntry())
435 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
437 ID.AddPointer(CP->getConstVal());
438 ID.AddInteger(CP->getTargetFlags());
442 const LoadSDNode *LD = cast<LoadSDNode>(N);
443 ID.AddInteger(LD->getMemoryVT().getRawBits());
444 ID.AddInteger(LD->getRawSubclassData());
448 const StoreSDNode *ST = cast<StoreSDNode>(N);
449 ID.AddInteger(ST->getMemoryVT().getRawBits());
450 ID.AddInteger(ST->getRawSubclassData());
453 case ISD::ATOMIC_CMP_SWAP:
454 case ISD::ATOMIC_SWAP:
455 case ISD::ATOMIC_LOAD_ADD:
456 case ISD::ATOMIC_LOAD_SUB:
457 case ISD::ATOMIC_LOAD_AND:
458 case ISD::ATOMIC_LOAD_OR:
459 case ISD::ATOMIC_LOAD_XOR:
460 case ISD::ATOMIC_LOAD_NAND:
461 case ISD::ATOMIC_LOAD_MIN:
462 case ISD::ATOMIC_LOAD_MAX:
463 case ISD::ATOMIC_LOAD_UMIN:
464 case ISD::ATOMIC_LOAD_UMAX:
465 case ISD::ATOMIC_LOAD:
466 case ISD::ATOMIC_STORE: {
467 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
468 ID.AddInteger(AT->getMemoryVT().getRawBits());
469 ID.AddInteger(AT->getRawSubclassData());
472 case ISD::VECTOR_SHUFFLE: {
473 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
474 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
476 ID.AddInteger(SVN->getMaskElt(i));
479 case ISD::TargetBlockAddress:
480 case ISD::BlockAddress: {
481 ID.AddPointer(cast<BlockAddressSDNode>(N)->getBlockAddress());
482 ID.AddInteger(cast<BlockAddressSDNode>(N)->getTargetFlags());
485 } // end switch (N->getOpcode())
488 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
490 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
491 AddNodeIDOpcode(ID, N->getOpcode());
492 // Add the return value info.
493 AddNodeIDValueTypes(ID, N->getVTList());
494 // Add the operand info.
495 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
497 // Handle SDNode leafs with special info.
498 AddNodeIDCustom(ID, N);
501 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
502 /// the CSE map that carries volatility, temporalness, indexing mode, and
503 /// extension/truncation information.
505 static inline unsigned
506 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
507 bool isNonTemporal, bool isInvariant) {
508 assert((ConvType & 3) == ConvType &&
509 "ConvType may not require more than 2 bits!");
510 assert((AM & 7) == AM &&
511 "AM may not require more than 3 bits!");
515 (isNonTemporal << 6) |
519 //===----------------------------------------------------------------------===//
520 // SelectionDAG Class
521 //===----------------------------------------------------------------------===//
523 /// doNotCSE - Return true if CSE should not be performed for this node.
524 static bool doNotCSE(SDNode *N) {
525 if (N->getValueType(0) == MVT::Glue)
526 return true; // Never CSE anything that produces a flag.
528 switch (N->getOpcode()) {
530 case ISD::HANDLENODE:
532 return true; // Never CSE these nodes.
535 // Check that remaining values produced are not flags.
536 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
537 if (N->getValueType(i) == MVT::Glue)
538 return true; // Never CSE anything that produces a flag.
543 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
545 void SelectionDAG::RemoveDeadNodes() {
546 // Create a dummy node (which is not added to allnodes), that adds a reference
547 // to the root node, preventing it from being deleted.
548 HandleSDNode Dummy(getRoot());
550 SmallVector<SDNode*, 128> DeadNodes;
552 // Add all obviously-dead nodes to the DeadNodes worklist.
553 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
555 DeadNodes.push_back(I);
557 RemoveDeadNodes(DeadNodes);
559 // If the root changed (e.g. it was a dead load, update the root).
560 setRoot(Dummy.getValue());
563 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
564 /// given list, and any nodes that become unreachable as a result.
565 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
567 // Process the worklist, deleting the nodes and adding their uses to the
569 while (!DeadNodes.empty()) {
570 SDNode *N = DeadNodes.pop_back_val();
572 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
573 DUL->NodeDeleted(N, 0);
575 // Take the node out of the appropriate CSE map.
576 RemoveNodeFromCSEMaps(N);
578 // Next, brutally remove the operand list. This is safe to do, as there are
579 // no cycles in the graph.
580 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
582 SDNode *Operand = Use.getNode();
585 // Now that we removed this operand, see if there are no uses of it left.
586 if (Operand->use_empty())
587 DeadNodes.push_back(Operand);
594 void SelectionDAG::RemoveDeadNode(SDNode *N){
595 SmallVector<SDNode*, 16> DeadNodes(1, N);
597 // Create a dummy node that adds a reference to the root node, preventing
598 // it from being deleted. (This matters if the root is an operand of the
600 HandleSDNode Dummy(getRoot());
602 RemoveDeadNodes(DeadNodes);
605 void SelectionDAG::DeleteNode(SDNode *N) {
606 // First take this out of the appropriate CSE map.
607 RemoveNodeFromCSEMaps(N);
609 // Finally, remove uses due to operands of this node, remove from the
610 // AllNodes list, and delete the node.
611 DeleteNodeNotInCSEMaps(N);
614 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
615 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
616 assert(N->use_empty() && "Cannot delete a node that is not dead!");
618 // Drop all of the operands and decrement used node's use counts.
624 void SelectionDAG::DeallocateNode(SDNode *N) {
625 if (N->OperandsNeedDelete)
626 delete[] N->OperandList;
628 // Set the opcode to DELETED_NODE to help catch bugs when node
629 // memory is reallocated.
630 N->NodeType = ISD::DELETED_NODE;
632 NodeAllocator.Deallocate(AllNodes.remove(N));
634 // Remove the ordering of this node.
637 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
638 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
639 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
640 DbgVals[i]->setIsInvalidated();
643 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
644 /// correspond to it. This is useful when we're about to delete or repurpose
645 /// the node. We don't want future request for structurally identical nodes
646 /// to return N anymore.
647 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
649 switch (N->getOpcode()) {
650 case ISD::HANDLENODE: return false; // noop.
652 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
653 "Cond code doesn't exist!");
654 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
655 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
657 case ISD::ExternalSymbol:
658 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
660 case ISD::TargetExternalSymbol: {
661 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
662 Erased = TargetExternalSymbols.erase(
663 std::pair<std::string,unsigned char>(ESN->getSymbol(),
664 ESN->getTargetFlags()));
667 case ISD::VALUETYPE: {
668 EVT VT = cast<VTSDNode>(N)->getVT();
669 if (VT.isExtended()) {
670 Erased = ExtendedValueTypeNodes.erase(VT);
672 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
673 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
678 // Remove it from the CSE Map.
679 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
680 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
681 Erased = CSEMap.RemoveNode(N);
685 // Verify that the node was actually in one of the CSE maps, unless it has a
686 // flag result (which cannot be CSE'd) or is one of the special cases that are
687 // not subject to CSE.
688 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
689 !N->isMachineOpcode() && !doNotCSE(N)) {
692 llvm_unreachable("Node is not in map!");
698 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
699 /// maps and modified in place. Add it back to the CSE maps, unless an identical
700 /// node already exists, in which case transfer all its users to the existing
701 /// node. This transfer can potentially trigger recursive merging.
704 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
705 // For node types that aren't CSE'd, just act as if no identical node
708 SDNode *Existing = CSEMap.GetOrInsertNode(N);
710 // If there was already an existing matching node, use ReplaceAllUsesWith
711 // to replace the dead one with the existing one. This can cause
712 // recursive merging of other unrelated nodes down the line.
713 ReplaceAllUsesWith(N, Existing);
715 // N is now dead. Inform the listeners and delete it.
716 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
717 DUL->NodeDeleted(N, Existing);
718 DeleteNodeNotInCSEMaps(N);
723 // If the node doesn't already exist, we updated it. Inform listeners.
724 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
728 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
729 /// were replaced with those specified. If this node is never memoized,
730 /// return null, otherwise return a pointer to the slot it would take. If a
731 /// node already exists with these operands, the slot will be non-null.
732 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
737 SDValue Ops[] = { Op };
739 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
740 AddNodeIDCustom(ID, N);
741 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
745 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
746 /// were replaced with those specified. If this node is never memoized,
747 /// return null, otherwise return a pointer to the slot it would take. If a
748 /// node already exists with these operands, the slot will be non-null.
749 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
750 SDValue Op1, SDValue Op2,
755 SDValue Ops[] = { Op1, Op2 };
757 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
758 AddNodeIDCustom(ID, N);
759 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
764 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
765 /// were replaced with those specified. If this node is never memoized,
766 /// return null, otherwise return a pointer to the slot it would take. If a
767 /// node already exists with these operands, the slot will be non-null.
768 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
769 const SDValue *Ops,unsigned NumOps,
775 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
776 AddNodeIDCustom(ID, N);
777 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
782 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
783 static void VerifyNodeCommon(SDNode *N) {
784 switch (N->getOpcode()) {
787 case ISD::BUILD_PAIR: {
788 EVT VT = N->getValueType(0);
789 assert(N->getNumValues() == 1 && "Too many results!");
790 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
791 "Wrong return type!");
792 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
793 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
794 "Mismatched operand types!");
795 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
796 "Wrong operand type!");
797 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
798 "Wrong return type size");
801 case ISD::BUILD_VECTOR: {
802 assert(N->getNumValues() == 1 && "Too many results!");
803 assert(N->getValueType(0).isVector() && "Wrong return type!");
804 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
805 "Wrong number of operands!");
806 EVT EltVT = N->getValueType(0).getVectorElementType();
807 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
808 assert((I->getValueType() == EltVT ||
809 (EltVT.isInteger() && I->getValueType().isInteger() &&
810 EltVT.bitsLE(I->getValueType()))) &&
811 "Wrong operand type!");
812 assert(I->getValueType() == N->getOperand(0).getValueType() &&
813 "Operands must all have the same type");
820 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
821 static void VerifySDNode(SDNode *N) {
822 // The SDNode allocators cannot be used to allocate nodes with fields that are
823 // not present in an SDNode!
824 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
825 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
826 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
827 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
828 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
829 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
830 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
831 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
832 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
833 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
834 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
835 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
836 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
837 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
838 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
839 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
840 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
841 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
842 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
847 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
849 static void VerifyMachineNode(SDNode *N) {
850 // The MachineNode allocators cannot be used to allocate nodes with fields
851 // that are not present in a MachineNode!
852 // Currently there are no such nodes.
858 /// getEVTAlignment - Compute the default alignment value for the
861 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
862 Type *Ty = VT == MVT::iPTR ?
863 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
864 VT.getTypeForEVT(*getContext());
866 return TLI.getTargetData()->getABITypeAlignment(Ty);
869 // EntryNode could meaningfully have debug info if we can find it...
870 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
871 : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
872 OptLevel(OL), EntryNode(ISD::EntryToken, DebugLoc(), getVTList(MVT::Other)),
873 Root(getEntryNode()), Ordering(0), UpdateListeners(0) {
874 AllNodes.push_back(&EntryNode);
875 Ordering = new SDNodeOrdering();
876 DbgInfo = new SDDbgInfo();
879 void SelectionDAG::init(MachineFunction &mf) {
881 Context = &mf.getFunction()->getContext();
884 SelectionDAG::~SelectionDAG() {
885 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
891 void SelectionDAG::allnodes_clear() {
892 assert(&*AllNodes.begin() == &EntryNode);
893 AllNodes.remove(AllNodes.begin());
894 while (!AllNodes.empty())
895 DeallocateNode(AllNodes.begin());
898 void SelectionDAG::clear() {
900 OperandAllocator.Reset();
903 ExtendedValueTypeNodes.clear();
904 ExternalSymbols.clear();
905 TargetExternalSymbols.clear();
906 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
907 static_cast<CondCodeSDNode*>(0));
908 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
909 static_cast<SDNode*>(0));
911 EntryNode.UseList = 0;
912 AllNodes.push_back(&EntryNode);
913 Root = getEntryNode();
918 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
919 return VT.bitsGT(Op.getValueType()) ?
920 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
921 getNode(ISD::TRUNCATE, DL, VT, Op);
924 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
925 return VT.bitsGT(Op.getValueType()) ?
926 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
927 getNode(ISD::TRUNCATE, DL, VT, Op);
930 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
931 return VT.bitsGT(Op.getValueType()) ?
932 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
933 getNode(ISD::TRUNCATE, DL, VT, Op);
936 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
937 assert(!VT.isVector() &&
938 "getZeroExtendInReg should use the vector element type instead of "
940 if (Op.getValueType() == VT) return Op;
941 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
942 APInt Imm = APInt::getLowBitsSet(BitWidth,
944 return getNode(ISD::AND, DL, Op.getValueType(), Op,
945 getConstant(Imm, Op.getValueType()));
948 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
950 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
951 EVT EltVT = VT.getScalarType();
953 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
954 return getNode(ISD::XOR, DL, VT, Val, NegOne);
957 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
958 EVT EltVT = VT.getScalarType();
959 assert((EltVT.getSizeInBits() >= 64 ||
960 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
961 "getConstant with a uint64_t value that doesn't fit in the type!");
962 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
965 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
966 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
969 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
970 assert(VT.isInteger() && "Cannot create FP integer constant!");
972 EVT EltVT = VT.getScalarType();
973 const ConstantInt *Elt = &Val;
975 // In some cases the vector type is legal but the element type is illegal and
976 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
977 // inserted value (the type does not need to match the vector element type).
978 // Any extra bits introduced will be truncated away.
979 if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
980 TargetLowering::TypePromoteInteger) {
981 EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
982 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
983 Elt = ConstantInt::get(*getContext(), NewVal);
986 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
987 "APInt size does not match type size!");
988 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
990 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
994 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
996 return SDValue(N, 0);
999 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1000 CSEMap.InsertNode(N, IP);
1001 AllNodes.push_back(N);
1004 SDValue Result(N, 0);
1005 if (VT.isVector()) {
1006 SmallVector<SDValue, 8> Ops;
1007 Ops.assign(VT.getVectorNumElements(), Result);
1008 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1013 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1014 return getConstant(Val, TLI.getPointerTy(), isTarget);
1018 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1019 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1022 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1023 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1025 EVT EltVT = VT.getScalarType();
1027 // Do the map lookup using the actual bit pattern for the floating point
1028 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1029 // we don't have issues with SNANs.
1030 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1031 FoldingSetNodeID ID;
1032 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1036 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1038 return SDValue(N, 0);
1041 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1042 CSEMap.InsertNode(N, IP);
1043 AllNodes.push_back(N);
1046 SDValue Result(N, 0);
1047 if (VT.isVector()) {
1048 SmallVector<SDValue, 8> Ops;
1049 Ops.assign(VT.getVectorNumElements(), Result);
1050 // FIXME DebugLoc info might be appropriate here
1051 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1056 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1057 EVT EltVT = VT.getScalarType();
1058 if (EltVT==MVT::f32)
1059 return getConstantFP(APFloat((float)Val), VT, isTarget);
1060 else if (EltVT==MVT::f64)
1061 return getConstantFP(APFloat(Val), VT, isTarget);
1062 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::f16) {
1064 APFloat apf = APFloat(Val);
1065 apf.convert(*EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1067 return getConstantFP(apf, VT, isTarget);
1069 llvm_unreachable("Unsupported type in getConstantFP");
1072 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1073 EVT VT, int64_t Offset,
1075 unsigned char TargetFlags) {
1076 assert((TargetFlags == 0 || isTargetGA) &&
1077 "Cannot set target flags on target-independent globals");
1079 // Truncate (with sign-extension) the offset value to the pointer size.
1080 EVT PTy = TLI.getPointerTy();
1081 unsigned BitWidth = PTy.getSizeInBits();
1083 Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth));
1085 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1087 // If GV is an alias then use the aliasee for determining thread-localness.
1088 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1089 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1093 if (GVar && GVar->isThreadLocal())
1094 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1096 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1098 FoldingSetNodeID ID;
1099 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1101 ID.AddInteger(Offset);
1102 ID.AddInteger(TargetFlags);
1104 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1105 return SDValue(E, 0);
1107 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1108 Offset, TargetFlags);
1109 CSEMap.InsertNode(N, IP);
1110 AllNodes.push_back(N);
1111 return SDValue(N, 0);
1114 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1115 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1116 FoldingSetNodeID ID;
1117 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1120 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1121 return SDValue(E, 0);
1123 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1124 CSEMap.InsertNode(N, IP);
1125 AllNodes.push_back(N);
1126 return SDValue(N, 0);
1129 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1130 unsigned char TargetFlags) {
1131 assert((TargetFlags == 0 || isTarget) &&
1132 "Cannot set target flags on target-independent jump tables");
1133 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1134 FoldingSetNodeID ID;
1135 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1137 ID.AddInteger(TargetFlags);
1139 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1140 return SDValue(E, 0);
1142 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1144 CSEMap.InsertNode(N, IP);
1145 AllNodes.push_back(N);
1146 return SDValue(N, 0);
1149 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1150 unsigned Alignment, int Offset,
1152 unsigned char TargetFlags) {
1153 assert((TargetFlags == 0 || isTarget) &&
1154 "Cannot set target flags on target-independent globals");
1156 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1157 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1158 FoldingSetNodeID ID;
1159 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1160 ID.AddInteger(Alignment);
1161 ID.AddInteger(Offset);
1163 ID.AddInteger(TargetFlags);
1165 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1166 return SDValue(E, 0);
1168 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1169 Alignment, TargetFlags);
1170 CSEMap.InsertNode(N, IP);
1171 AllNodes.push_back(N);
1172 return SDValue(N, 0);
1176 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1177 unsigned Alignment, int Offset,
1179 unsigned char TargetFlags) {
1180 assert((TargetFlags == 0 || isTarget) &&
1181 "Cannot set target flags on target-independent globals");
1183 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1184 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1185 FoldingSetNodeID ID;
1186 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1187 ID.AddInteger(Alignment);
1188 ID.AddInteger(Offset);
1189 C->addSelectionDAGCSEId(ID);
1190 ID.AddInteger(TargetFlags);
1192 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1193 return SDValue(E, 0);
1195 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1196 Alignment, TargetFlags);
1197 CSEMap.InsertNode(N, IP);
1198 AllNodes.push_back(N);
1199 return SDValue(N, 0);
1202 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1203 FoldingSetNodeID ID;
1204 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1207 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1208 return SDValue(E, 0);
1210 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1211 CSEMap.InsertNode(N, IP);
1212 AllNodes.push_back(N);
1213 return SDValue(N, 0);
1216 SDValue SelectionDAG::getValueType(EVT VT) {
1217 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1218 ValueTypeNodes.size())
1219 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1221 SDNode *&N = VT.isExtended() ?
1222 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1224 if (N) return SDValue(N, 0);
1225 N = new (NodeAllocator) VTSDNode(VT);
1226 AllNodes.push_back(N);
1227 return SDValue(N, 0);
1230 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1231 SDNode *&N = ExternalSymbols[Sym];
1232 if (N) return SDValue(N, 0);
1233 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1234 AllNodes.push_back(N);
1235 return SDValue(N, 0);
1238 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1239 unsigned char TargetFlags) {
1241 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1243 if (N) return SDValue(N, 0);
1244 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1245 AllNodes.push_back(N);
1246 return SDValue(N, 0);
1249 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1250 if ((unsigned)Cond >= CondCodeNodes.size())
1251 CondCodeNodes.resize(Cond+1);
1253 if (CondCodeNodes[Cond] == 0) {
1254 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1255 CondCodeNodes[Cond] = N;
1256 AllNodes.push_back(N);
1259 return SDValue(CondCodeNodes[Cond], 0);
1262 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1263 // the shuffle mask M that point at N1 to point at N2, and indices that point
1264 // N2 to point at N1.
1265 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1267 int NElts = M.size();
1268 for (int i = 0; i != NElts; ++i) {
1276 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1277 SDValue N2, const int *Mask) {
1278 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1279 assert(VT.isVector() && N1.getValueType().isVector() &&
1280 "Vector Shuffle VTs must be a vectors");
1281 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1282 && "Vector Shuffle VTs must have same element type");
1284 // Canonicalize shuffle undef, undef -> undef
1285 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1286 return getUNDEF(VT);
1288 // Validate that all indices in Mask are within the range of the elements
1289 // input to the shuffle.
1290 unsigned NElts = VT.getVectorNumElements();
1291 SmallVector<int, 8> MaskVec;
1292 for (unsigned i = 0; i != NElts; ++i) {
1293 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1294 MaskVec.push_back(Mask[i]);
1297 // Canonicalize shuffle v, v -> v, undef
1300 for (unsigned i = 0; i != NElts; ++i)
1301 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1304 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1305 if (N1.getOpcode() == ISD::UNDEF)
1306 commuteShuffle(N1, N2, MaskVec);
1308 // Canonicalize all index into lhs, -> shuffle lhs, undef
1309 // Canonicalize all index into rhs, -> shuffle rhs, undef
1310 bool AllLHS = true, AllRHS = true;
1311 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1312 for (unsigned i = 0; i != NElts; ++i) {
1313 if (MaskVec[i] >= (int)NElts) {
1318 } else if (MaskVec[i] >= 0) {
1322 if (AllLHS && AllRHS)
1323 return getUNDEF(VT);
1324 if (AllLHS && !N2Undef)
1328 commuteShuffle(N1, N2, MaskVec);
1331 // If Identity shuffle, or all shuffle in to undef, return that node.
1332 bool AllUndef = true;
1333 bool Identity = true;
1334 for (unsigned i = 0; i != NElts; ++i) {
1335 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1336 if (MaskVec[i] >= 0) AllUndef = false;
1338 if (Identity && NElts == N1.getValueType().getVectorNumElements())
1341 return getUNDEF(VT);
1343 FoldingSetNodeID ID;
1344 SDValue Ops[2] = { N1, N2 };
1345 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1346 for (unsigned i = 0; i != NElts; ++i)
1347 ID.AddInteger(MaskVec[i]);
1350 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1351 return SDValue(E, 0);
1353 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1354 // SDNode doesn't have access to it. This memory will be "leaked" when
1355 // the node is deallocated, but recovered when the NodeAllocator is released.
1356 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1357 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1359 ShuffleVectorSDNode *N =
1360 new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1361 CSEMap.InsertNode(N, IP);
1362 AllNodes.push_back(N);
1363 return SDValue(N, 0);
1366 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1367 SDValue Val, SDValue DTy,
1368 SDValue STy, SDValue Rnd, SDValue Sat,
1369 ISD::CvtCode Code) {
1370 // If the src and dest types are the same and the conversion is between
1371 // integer types of the same sign or two floats, no conversion is necessary.
1373 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1376 FoldingSetNodeID ID;
1377 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1378 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1380 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1381 return SDValue(E, 0);
1383 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1385 CSEMap.InsertNode(N, IP);
1386 AllNodes.push_back(N);
1387 return SDValue(N, 0);
1390 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1391 FoldingSetNodeID ID;
1392 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1393 ID.AddInteger(RegNo);
1395 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1396 return SDValue(E, 0);
1398 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1399 CSEMap.InsertNode(N, IP);
1400 AllNodes.push_back(N);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1405 FoldingSetNodeID ID;
1406 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1407 ID.AddPointer(RegMask);
1409 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1410 return SDValue(E, 0);
1412 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1413 CSEMap.InsertNode(N, IP);
1414 AllNodes.push_back(N);
1415 return SDValue(N, 0);
1418 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1419 FoldingSetNodeID ID;
1420 SDValue Ops[] = { Root };
1421 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1422 ID.AddPointer(Label);
1424 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1425 return SDValue(E, 0);
1427 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1428 CSEMap.InsertNode(N, IP);
1429 AllNodes.push_back(N);
1430 return SDValue(N, 0);
1434 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1436 unsigned char TargetFlags) {
1437 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1439 FoldingSetNodeID ID;
1440 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1442 ID.AddInteger(TargetFlags);
1444 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1445 return SDValue(E, 0);
1447 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, TargetFlags);
1448 CSEMap.InsertNode(N, IP);
1449 AllNodes.push_back(N);
1450 return SDValue(N, 0);
1453 SDValue SelectionDAG::getSrcValue(const Value *V) {
1454 assert((!V || V->getType()->isPointerTy()) &&
1455 "SrcValue is not a pointer?");
1457 FoldingSetNodeID ID;
1458 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1462 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1463 return SDValue(E, 0);
1465 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1466 CSEMap.InsertNode(N, IP);
1467 AllNodes.push_back(N);
1468 return SDValue(N, 0);
1471 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1472 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1473 FoldingSetNodeID ID;
1474 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1478 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1479 return SDValue(E, 0);
1481 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1482 CSEMap.InsertNode(N, IP);
1483 AllNodes.push_back(N);
1484 return SDValue(N, 0);
1488 /// getShiftAmountOperand - Return the specified value casted to
1489 /// the target's desired shift amount type.
1490 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1491 EVT OpTy = Op.getValueType();
1492 MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1493 if (OpTy == ShTy || OpTy.isVector()) return Op;
1495 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1496 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1499 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1500 /// specified value type.
1501 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1502 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1503 unsigned ByteSize = VT.getStoreSize();
1504 Type *Ty = VT.getTypeForEVT(*getContext());
1505 unsigned StackAlign =
1506 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1508 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1509 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1512 /// CreateStackTemporary - Create a stack temporary suitable for holding
1513 /// either of the specified value types.
1514 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1515 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1516 VT2.getStoreSizeInBits())/8;
1517 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1518 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1519 const TargetData *TD = TLI.getTargetData();
1520 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1521 TD->getPrefTypeAlignment(Ty2));
1523 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1524 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1525 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1528 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1529 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1530 // These setcc operations always fold.
1534 case ISD::SETFALSE2: return getConstant(0, VT);
1536 case ISD::SETTRUE2: return getConstant(1, VT);
1548 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1552 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1553 const APInt &C2 = N2C->getAPIntValue();
1554 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1555 const APInt &C1 = N1C->getAPIntValue();
1558 default: llvm_unreachable("Unknown integer setcc!");
1559 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1560 case ISD::SETNE: return getConstant(C1 != C2, VT);
1561 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1562 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1563 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1564 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1565 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1566 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1567 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1568 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1572 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1573 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1574 // No compile time operations on this type yet.
1575 if (N1C->getValueType(0) == MVT::ppcf128)
1578 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1581 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1582 return getUNDEF(VT);
1584 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1585 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1586 return getUNDEF(VT);
1588 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1589 R==APFloat::cmpLessThan, VT);
1590 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1591 return getUNDEF(VT);
1593 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1594 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1595 return getUNDEF(VT);
1597 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1598 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1599 return getUNDEF(VT);
1601 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1602 R==APFloat::cmpEqual, VT);
1603 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1604 return getUNDEF(VT);
1606 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1607 R==APFloat::cmpEqual, VT);
1608 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1609 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1610 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1611 R==APFloat::cmpEqual, VT);
1612 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1613 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1614 R==APFloat::cmpLessThan, VT);
1615 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1616 R==APFloat::cmpUnordered, VT);
1617 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1618 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1621 // Ensure that the constant occurs on the RHS.
1622 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1626 // Could not fold it.
1630 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1631 /// use this predicate to simplify operations downstream.
1632 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1633 // This predicate is not safe for vector operations.
1634 if (Op.getValueType().isVector())
1637 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1638 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1641 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1642 /// this predicate to simplify operations downstream. Mask is known to be zero
1643 /// for bits that V cannot have.
1644 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1645 unsigned Depth) const {
1646 APInt KnownZero, KnownOne;
1647 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1648 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1649 return (KnownZero & Mask) == Mask;
1652 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1653 /// known to be either zero or one and return them in the KnownZero/KnownOne
1654 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1656 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1657 APInt &KnownOne, unsigned Depth) const {
1658 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1660 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1662 return; // Limit search depth.
1664 APInt KnownZero2, KnownOne2;
1666 switch (Op.getOpcode()) {
1668 // We know all of the bits for a constant!
1669 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1670 KnownZero = ~KnownOne;
1673 // If either the LHS or the RHS are Zero, the result is zero.
1674 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1675 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1676 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1677 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1679 // Output known-1 bits are only known if set in both the LHS & RHS.
1680 KnownOne &= KnownOne2;
1681 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1682 KnownZero |= KnownZero2;
1685 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1686 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1687 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1688 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1690 // Output known-0 bits are only known if clear in both the LHS & RHS.
1691 KnownZero &= KnownZero2;
1692 // Output known-1 are known to be set if set in either the LHS | RHS.
1693 KnownOne |= KnownOne2;
1696 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1697 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1698 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1699 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1701 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1702 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1703 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1704 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1705 KnownZero = KnownZeroOut;
1709 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1710 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1711 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1712 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1714 // If low bits are zero in either operand, output low known-0 bits.
1715 // Also compute a conserative estimate for high known-0 bits.
1716 // More trickiness is possible, but this is sufficient for the
1717 // interesting case of alignment computation.
1718 KnownOne.clearAllBits();
1719 unsigned TrailZ = KnownZero.countTrailingOnes() +
1720 KnownZero2.countTrailingOnes();
1721 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1722 KnownZero2.countLeadingOnes(),
1723 BitWidth) - BitWidth;
1725 TrailZ = std::min(TrailZ, BitWidth);
1726 LeadZ = std::min(LeadZ, BitWidth);
1727 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1728 APInt::getHighBitsSet(BitWidth, LeadZ);
1732 // For the purposes of computing leading zeros we can conservatively
1733 // treat a udiv as a logical right shift by the power of 2 known to
1734 // be less than the denominator.
1735 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1736 unsigned LeadZ = KnownZero2.countLeadingOnes();
1738 KnownOne2.clearAllBits();
1739 KnownZero2.clearAllBits();
1740 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1741 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1742 if (RHSUnknownLeadingOnes != BitWidth)
1743 LeadZ = std::min(BitWidth,
1744 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1746 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1750 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1751 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1752 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1753 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1755 // Only known if known in both the LHS and RHS.
1756 KnownOne &= KnownOne2;
1757 KnownZero &= KnownZero2;
1759 case ISD::SELECT_CC:
1760 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1761 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1762 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1763 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1765 // Only known if known in both the LHS and RHS.
1766 KnownOne &= KnownOne2;
1767 KnownZero &= KnownZero2;
1775 if (Op.getResNo() != 1)
1777 // The boolean result conforms to getBooleanContents. Fall through.
1779 // If we know the result of a setcc has the top bits zero, use this info.
1780 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1781 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1782 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1785 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1786 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1787 unsigned ShAmt = SA->getZExtValue();
1789 // If the shift count is an invalid immediate, don't do anything.
1790 if (ShAmt >= BitWidth)
1793 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1794 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1795 KnownZero <<= ShAmt;
1797 // low bits known zero.
1798 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1802 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1803 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1804 unsigned ShAmt = SA->getZExtValue();
1806 // If the shift count is an invalid immediate, don't do anything.
1807 if (ShAmt >= BitWidth)
1810 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1811 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1812 KnownZero = KnownZero.lshr(ShAmt);
1813 KnownOne = KnownOne.lshr(ShAmt);
1815 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1816 KnownZero |= HighBits; // High bits known zero.
1820 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1821 unsigned ShAmt = SA->getZExtValue();
1823 // If the shift count is an invalid immediate, don't do anything.
1824 if (ShAmt >= BitWidth)
1827 // If any of the demanded bits are produced by the sign extension, we also
1828 // demand the input sign bit.
1829 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1831 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1832 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1833 KnownZero = KnownZero.lshr(ShAmt);
1834 KnownOne = KnownOne.lshr(ShAmt);
1836 // Handle the sign bits.
1837 APInt SignBit = APInt::getSignBit(BitWidth);
1838 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1840 if (KnownZero.intersects(SignBit)) {
1841 KnownZero |= HighBits; // New bits are known zero.
1842 } else if (KnownOne.intersects(SignBit)) {
1843 KnownOne |= HighBits; // New bits are known one.
1847 case ISD::SIGN_EXTEND_INREG: {
1848 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1849 unsigned EBits = EVT.getScalarType().getSizeInBits();
1851 // Sign extension. Compute the demanded bits in the result that are not
1852 // present in the input.
1853 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1855 APInt InSignBit = APInt::getSignBit(EBits);
1856 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1858 // If the sign extended bits are demanded, we know that the sign
1860 InSignBit = InSignBit.zext(BitWidth);
1861 if (NewBits.getBoolValue())
1862 InputDemandedBits |= InSignBit;
1864 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1865 KnownOne &= InputDemandedBits;
1866 KnownZero &= InputDemandedBits;
1867 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1869 // If the sign bit of the input is known set or clear, then we know the
1870 // top bits of the result.
1871 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1872 KnownZero |= NewBits;
1873 KnownOne &= ~NewBits;
1874 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1875 KnownOne |= NewBits;
1876 KnownZero &= ~NewBits;
1877 } else { // Input sign bit unknown
1878 KnownZero &= ~NewBits;
1879 KnownOne &= ~NewBits;
1884 case ISD::CTTZ_ZERO_UNDEF:
1886 case ISD::CTLZ_ZERO_UNDEF:
1888 unsigned LowBits = Log2_32(BitWidth)+1;
1889 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1890 KnownOne.clearAllBits();
1894 LoadSDNode *LD = cast<LoadSDNode>(Op);
1895 if (ISD::isZEXTLoad(Op.getNode())) {
1896 EVT VT = LD->getMemoryVT();
1897 unsigned MemBits = VT.getScalarType().getSizeInBits();
1898 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
1899 } else if (const MDNode *Ranges = LD->getRanges()) {
1900 computeMaskedBitsLoad(*Ranges, KnownZero);
1904 case ISD::ZERO_EXTEND: {
1905 EVT InVT = Op.getOperand(0).getValueType();
1906 unsigned InBits = InVT.getScalarType().getSizeInBits();
1907 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1908 KnownZero = KnownZero.trunc(InBits);
1909 KnownOne = KnownOne.trunc(InBits);
1910 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1911 KnownZero = KnownZero.zext(BitWidth);
1912 KnownOne = KnownOne.zext(BitWidth);
1913 KnownZero |= NewBits;
1916 case ISD::SIGN_EXTEND: {
1917 EVT InVT = Op.getOperand(0).getValueType();
1918 unsigned InBits = InVT.getScalarType().getSizeInBits();
1919 APInt InSignBit = APInt::getSignBit(InBits);
1920 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1922 KnownZero = KnownZero.trunc(InBits);
1923 KnownOne = KnownOne.trunc(InBits);
1924 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1926 // Note if the sign bit is known to be zero or one.
1927 bool SignBitKnownZero = KnownZero.isNegative();
1928 bool SignBitKnownOne = KnownOne.isNegative();
1929 assert(!(SignBitKnownZero && SignBitKnownOne) &&
1930 "Sign bit can't be known to be both zero and one!");
1932 KnownZero = KnownZero.zext(BitWidth);
1933 KnownOne = KnownOne.zext(BitWidth);
1935 // If the sign bit is known zero or one, the top bits match.
1936 if (SignBitKnownZero)
1937 KnownZero |= NewBits;
1938 else if (SignBitKnownOne)
1939 KnownOne |= NewBits;
1942 case ISD::ANY_EXTEND: {
1943 EVT InVT = Op.getOperand(0).getValueType();
1944 unsigned InBits = InVT.getScalarType().getSizeInBits();
1945 KnownZero = KnownZero.trunc(InBits);
1946 KnownOne = KnownOne.trunc(InBits);
1947 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1948 KnownZero = KnownZero.zext(BitWidth);
1949 KnownOne = KnownOne.zext(BitWidth);
1952 case ISD::TRUNCATE: {
1953 EVT InVT = Op.getOperand(0).getValueType();
1954 unsigned InBits = InVT.getScalarType().getSizeInBits();
1955 KnownZero = KnownZero.zext(InBits);
1956 KnownOne = KnownOne.zext(InBits);
1957 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1958 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1959 KnownZero = KnownZero.trunc(BitWidth);
1960 KnownOne = KnownOne.trunc(BitWidth);
1963 case ISD::AssertZext: {
1964 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1965 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
1966 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1967 KnownZero |= (~InMask);
1968 KnownOne &= (~KnownZero);
1972 // All bits are zero except the low bit.
1973 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1977 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1978 // We know that the top bits of C-X are clear if X contains less bits
1979 // than C (i.e. no wrap-around can happen). For example, 20-X is
1980 // positive if we can prove that X is >= 0 and < 16.
1981 if (CLHS->getAPIntValue().isNonNegative()) {
1982 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1983 // NLZ can't be BitWidth with no sign bit
1984 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1985 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1987 // If all of the MaskV bits are known to be zero, then we know the
1988 // output top bits are zero, because we now know that the output is
1990 if ((KnownZero2 & MaskV) == MaskV) {
1991 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1992 // Top bits known zero.
1993 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2001 // Output known-0 bits are known if clear or set in both the low clear bits
2002 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2003 // low 3 bits clear.
2004 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2005 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2006 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2008 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2009 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2010 KnownZeroOut = std::min(KnownZeroOut,
2011 KnownZero2.countTrailingOnes());
2013 if (Op.getOpcode() == ISD::ADD) {
2014 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2018 // With ADDE, a carry bit may be added in, so we can only use this
2019 // information if we know (at least) that the low two bits are clear. We
2020 // then return to the caller that the low bit is unknown but that other bits
2022 if (KnownZeroOut >= 2) // ADDE
2023 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2027 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2028 const APInt &RA = Rem->getAPIntValue().abs();
2029 if (RA.isPowerOf2()) {
2030 APInt LowBits = RA - 1;
2031 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2032 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2034 // The low bits of the first operand are unchanged by the srem.
2035 KnownZero = KnownZero2 & LowBits;
2036 KnownOne = KnownOne2 & LowBits;
2038 // If the first operand is non-negative or has all low bits zero, then
2039 // the upper bits are all zero.
2040 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2041 KnownZero |= ~LowBits;
2043 // If the first operand is negative and not all low bits are zero, then
2044 // the upper bits are all one.
2045 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2046 KnownOne |= ~LowBits;
2047 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2052 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2053 const APInt &RA = Rem->getAPIntValue();
2054 if (RA.isPowerOf2()) {
2055 APInt LowBits = (RA - 1);
2056 KnownZero |= ~LowBits;
2057 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2058 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2063 // Since the result is less than or equal to either operand, any leading
2064 // zero bits in either operand must also exist in the result.
2065 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2066 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2068 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2069 KnownZero2.countLeadingOnes());
2070 KnownOne.clearAllBits();
2071 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2074 case ISD::FrameIndex:
2075 case ISD::TargetFrameIndex:
2076 if (unsigned Align = InferPtrAlignment(Op)) {
2077 // The low bits are known zero if the pointer is aligned.
2078 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2084 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2087 case ISD::INTRINSIC_WO_CHAIN:
2088 case ISD::INTRINSIC_W_CHAIN:
2089 case ISD::INTRINSIC_VOID:
2090 // Allow the target to implement this method for its nodes.
2091 TLI.computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2096 /// ComputeNumSignBits - Return the number of times the sign bit of the
2097 /// register is replicated into the other bits. We know that at least 1 bit
2098 /// is always equal to the sign bit (itself), but other cases can give us
2099 /// information. For example, immediately after an "SRA X, 2", we know that
2100 /// the top 3 bits are all equal to each other, so we return 3.
2101 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2102 EVT VT = Op.getValueType();
2103 assert(VT.isInteger() && "Invalid VT!");
2104 unsigned VTBits = VT.getScalarType().getSizeInBits();
2106 unsigned FirstAnswer = 1;
2109 return 1; // Limit search depth.
2111 switch (Op.getOpcode()) {
2113 case ISD::AssertSext:
2114 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2115 return VTBits-Tmp+1;
2116 case ISD::AssertZext:
2117 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2120 case ISD::Constant: {
2121 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2122 return Val.getNumSignBits();
2125 case ISD::SIGN_EXTEND:
2126 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2127 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2129 case ISD::SIGN_EXTEND_INREG:
2130 // Max of the input and what this extends.
2132 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2135 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2136 return std::max(Tmp, Tmp2);
2139 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2140 // SRA X, C -> adds C sign bits.
2141 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2142 Tmp += C->getZExtValue();
2143 if (Tmp > VTBits) Tmp = VTBits;
2147 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2148 // shl destroys sign bits.
2149 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2150 if (C->getZExtValue() >= VTBits || // Bad shift.
2151 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2152 return Tmp - C->getZExtValue();
2157 case ISD::XOR: // NOT is handled here.
2158 // Logical binary ops preserve the number of sign bits at the worst.
2159 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2161 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2162 FirstAnswer = std::min(Tmp, Tmp2);
2163 // We computed what we know about the sign bits as our first
2164 // answer. Now proceed to the generic code that uses
2165 // ComputeMaskedBits, and pick whichever answer is better.
2170 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2171 if (Tmp == 1) return 1; // Early out.
2172 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2173 return std::min(Tmp, Tmp2);
2181 if (Op.getResNo() != 1)
2183 // The boolean result conforms to getBooleanContents. Fall through.
2185 // If setcc returns 0/-1, all bits are sign bits.
2186 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2187 TargetLowering::ZeroOrNegativeOneBooleanContent)
2192 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2193 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2195 // Handle rotate right by N like a rotate left by 32-N.
2196 if (Op.getOpcode() == ISD::ROTR)
2197 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2199 // If we aren't rotating out all of the known-in sign bits, return the
2200 // number that are left. This handles rotl(sext(x), 1) for example.
2201 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2202 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2206 // Add can have at most one carry bit. Thus we know that the output
2207 // is, at worst, one more bit than the inputs.
2208 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2209 if (Tmp == 1) return 1; // Early out.
2211 // Special case decrementing a value (ADD X, -1):
2212 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2213 if (CRHS->isAllOnesValue()) {
2214 APInt KnownZero, KnownOne;
2215 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2217 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2219 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2222 // If we are subtracting one from a positive number, there is no carry
2223 // out of the result.
2224 if (KnownZero.isNegative())
2228 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2229 if (Tmp2 == 1) return 1;
2230 return std::min(Tmp, Tmp2)-1;
2233 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2234 if (Tmp2 == 1) return 1;
2237 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2238 if (CLHS->isNullValue()) {
2239 APInt KnownZero, KnownOne;
2240 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2241 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2243 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2246 // If the input is known to be positive (the sign bit is known clear),
2247 // the output of the NEG has the same number of sign bits as the input.
2248 if (KnownZero.isNegative())
2251 // Otherwise, we treat this like a SUB.
2254 // Sub can have at most one carry bit. Thus we know that the output
2255 // is, at worst, one more bit than the inputs.
2256 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2257 if (Tmp == 1) return 1; // Early out.
2258 return std::min(Tmp, Tmp2)-1;
2260 // FIXME: it's tricky to do anything useful for this, but it is an important
2261 // case for targets like X86.
2265 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2266 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2267 unsigned ExtType = LD->getExtensionType();
2270 case ISD::SEXTLOAD: // '17' bits known
2271 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2272 return VTBits-Tmp+1;
2273 case ISD::ZEXTLOAD: // '16' bits known
2274 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2279 // Allow the target to implement this method for its nodes.
2280 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2281 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2282 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2283 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2284 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2285 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2288 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2289 // use this information.
2290 APInt KnownZero, KnownOne;
2291 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2294 if (KnownZero.isNegative()) { // sign bit is 0
2296 } else if (KnownOne.isNegative()) { // sign bit is 1;
2303 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2304 // the number of identical bits in the top of the input value.
2306 Mask <<= Mask.getBitWidth()-VTBits;
2307 // Return # leading zeros. We use 'min' here in case Val was zero before
2308 // shifting. We don't want to return '64' as for an i32 "0".
2309 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2312 /// isBaseWithConstantOffset - Return true if the specified operand is an
2313 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2314 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2315 /// semantics as an ADD. This handles the equivalence:
2316 /// X|Cst == X+Cst iff X&Cst = 0.
2317 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2318 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2319 !isa<ConstantSDNode>(Op.getOperand(1)))
2322 if (Op.getOpcode() == ISD::OR &&
2323 !MaskedValueIsZero(Op.getOperand(0),
2324 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2331 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2332 // If we're told that NaNs won't happen, assume they won't.
2333 if (getTarget().Options.NoNaNsFPMath)
2336 // If the value is a constant, we can obviously see if it is a NaN or not.
2337 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2338 return !C->getValueAPF().isNaN();
2340 // TODO: Recognize more cases here.
2345 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2346 // If the value is a constant, we can obviously see if it is a zero or not.
2347 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2348 return !C->isZero();
2350 // TODO: Recognize more cases here.
2351 switch (Op.getOpcode()) {
2354 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2355 return !C->isNullValue();
2362 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2363 // Check the obvious case.
2364 if (A == B) return true;
2366 // For for negative and positive zero.
2367 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2368 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2369 if (CA->isZero() && CB->isZero()) return true;
2371 // Otherwise they may not be equal.
2375 /// getNode - Gets or creates the specified node.
2377 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2378 FoldingSetNodeID ID;
2379 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2381 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2382 return SDValue(E, 0);
2384 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2385 CSEMap.InsertNode(N, IP);
2387 AllNodes.push_back(N);
2391 return SDValue(N, 0);
2394 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2395 EVT VT, SDValue Operand) {
2396 // Constant fold unary operations with an integer constant operand.
2397 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2398 const APInt &Val = C->getAPIntValue();
2401 case ISD::SIGN_EXTEND:
2402 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2403 case ISD::ANY_EXTEND:
2404 case ISD::ZERO_EXTEND:
2406 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2407 case ISD::UINT_TO_FP:
2408 case ISD::SINT_TO_FP: {
2409 // No compile time operations on ppcf128.
2410 if (VT == MVT::ppcf128) break;
2411 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2412 (void)apf.convertFromAPInt(Val,
2413 Opcode==ISD::SINT_TO_FP,
2414 APFloat::rmNearestTiesToEven);
2415 return getConstantFP(apf, VT);
2418 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2419 return getConstantFP(Val.bitsToFloat(), VT);
2420 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2421 return getConstantFP(Val.bitsToDouble(), VT);
2424 return getConstant(Val.byteSwap(), VT);
2426 return getConstant(Val.countPopulation(), VT);
2428 case ISD::CTLZ_ZERO_UNDEF:
2429 return getConstant(Val.countLeadingZeros(), VT);
2431 case ISD::CTTZ_ZERO_UNDEF:
2432 return getConstant(Val.countTrailingZeros(), VT);
2436 // Constant fold unary operations with a floating point constant operand.
2437 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2438 APFloat V = C->getValueAPF(); // make copy
2439 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2443 return getConstantFP(V, VT);
2446 return getConstantFP(V, VT);
2447 case ISD::FP_EXTEND: {
2449 // This can return overflow, underflow, or inexact; we don't care.
2450 // FIXME need to be more flexible about rounding mode.
2451 (void)V.convert(*EVTToAPFloatSemantics(VT),
2452 APFloat::rmNearestTiesToEven, &ignored);
2453 return getConstantFP(V, VT);
2455 case ISD::FP_TO_SINT:
2456 case ISD::FP_TO_UINT: {
2459 assert(integerPartWidth >= 64);
2460 // FIXME need to be more flexible about rounding mode.
2461 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2462 Opcode==ISD::FP_TO_SINT,
2463 APFloat::rmTowardZero, &ignored);
2464 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2466 APInt api(VT.getSizeInBits(), x);
2467 return getConstant(api, VT);
2470 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2471 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2472 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2473 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2479 unsigned OpOpcode = Operand.getNode()->getOpcode();
2481 case ISD::TokenFactor:
2482 case ISD::MERGE_VALUES:
2483 case ISD::CONCAT_VECTORS:
2484 return Operand; // Factor, merge or concat of one node? No need.
2485 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2486 case ISD::FP_EXTEND:
2487 assert(VT.isFloatingPoint() &&
2488 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2489 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2490 assert((!VT.isVector() ||
2491 VT.getVectorNumElements() ==
2492 Operand.getValueType().getVectorNumElements()) &&
2493 "Vector element count mismatch!");
2494 if (Operand.getOpcode() == ISD::UNDEF)
2495 return getUNDEF(VT);
2497 case ISD::SIGN_EXTEND:
2498 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2499 "Invalid SIGN_EXTEND!");
2500 if (Operand.getValueType() == VT) return Operand; // noop extension
2501 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2502 "Invalid sext node, dst < src!");
2503 assert((!VT.isVector() ||
2504 VT.getVectorNumElements() ==
2505 Operand.getValueType().getVectorNumElements()) &&
2506 "Vector element count mismatch!");
2507 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2508 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2509 else if (OpOpcode == ISD::UNDEF)
2510 // sext(undef) = 0, because the top bits will all be the same.
2511 return getConstant(0, VT);
2513 case ISD::ZERO_EXTEND:
2514 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2515 "Invalid ZERO_EXTEND!");
2516 if (Operand.getValueType() == VT) return Operand; // noop extension
2517 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2518 "Invalid zext node, dst < src!");
2519 assert((!VT.isVector() ||
2520 VT.getVectorNumElements() ==
2521 Operand.getValueType().getVectorNumElements()) &&
2522 "Vector element count mismatch!");
2523 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2524 return getNode(ISD::ZERO_EXTEND, DL, VT,
2525 Operand.getNode()->getOperand(0));
2526 else if (OpOpcode == ISD::UNDEF)
2527 // zext(undef) = 0, because the top bits will be zero.
2528 return getConstant(0, VT);
2530 case ISD::ANY_EXTEND:
2531 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2532 "Invalid ANY_EXTEND!");
2533 if (Operand.getValueType() == VT) return Operand; // noop extension
2534 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2535 "Invalid anyext node, dst < src!");
2536 assert((!VT.isVector() ||
2537 VT.getVectorNumElements() ==
2538 Operand.getValueType().getVectorNumElements()) &&
2539 "Vector element count mismatch!");
2541 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2542 OpOpcode == ISD::ANY_EXTEND)
2543 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2544 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2545 else if (OpOpcode == ISD::UNDEF)
2546 return getUNDEF(VT);
2548 // (ext (trunx x)) -> x
2549 if (OpOpcode == ISD::TRUNCATE) {
2550 SDValue OpOp = Operand.getNode()->getOperand(0);
2551 if (OpOp.getValueType() == VT)
2556 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2557 "Invalid TRUNCATE!");
2558 if (Operand.getValueType() == VT) return Operand; // noop truncate
2559 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2560 "Invalid truncate node, src < dst!");
2561 assert((!VT.isVector() ||
2562 VT.getVectorNumElements() ==
2563 Operand.getValueType().getVectorNumElements()) &&
2564 "Vector element count mismatch!");
2565 if (OpOpcode == ISD::TRUNCATE)
2566 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2567 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2568 OpOpcode == ISD::ANY_EXTEND) {
2569 // If the source is smaller than the dest, we still need an extend.
2570 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2571 .bitsLT(VT.getScalarType()))
2572 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2573 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2574 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2575 return Operand.getNode()->getOperand(0);
2577 if (OpOpcode == ISD::UNDEF)
2578 return getUNDEF(VT);
2581 // Basic sanity checking.
2582 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2583 && "Cannot BITCAST between types of different sizes!");
2584 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2585 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2586 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2587 if (OpOpcode == ISD::UNDEF)
2588 return getUNDEF(VT);
2590 case ISD::SCALAR_TO_VECTOR:
2591 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2592 (VT.getVectorElementType() == Operand.getValueType() ||
2593 (VT.getVectorElementType().isInteger() &&
2594 Operand.getValueType().isInteger() &&
2595 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2596 "Illegal SCALAR_TO_VECTOR node!");
2597 if (OpOpcode == ISD::UNDEF)
2598 return getUNDEF(VT);
2599 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2600 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2601 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2602 Operand.getConstantOperandVal(1) == 0 &&
2603 Operand.getOperand(0).getValueType() == VT)
2604 return Operand.getOperand(0);
2607 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2608 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2609 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2610 Operand.getNode()->getOperand(0));
2611 if (OpOpcode == ISD::FNEG) // --X -> X
2612 return Operand.getNode()->getOperand(0);
2615 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2616 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2621 SDVTList VTs = getVTList(VT);
2622 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2623 FoldingSetNodeID ID;
2624 SDValue Ops[1] = { Operand };
2625 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2627 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2628 return SDValue(E, 0);
2630 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2631 CSEMap.InsertNode(N, IP);
2633 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2636 AllNodes.push_back(N);
2640 return SDValue(N, 0);
2643 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2645 ConstantSDNode *Cst1,
2646 ConstantSDNode *Cst2) {
2647 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2650 case ISD::ADD: return getConstant(C1 + C2, VT);
2651 case ISD::SUB: return getConstant(C1 - C2, VT);
2652 case ISD::MUL: return getConstant(C1 * C2, VT);
2654 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2657 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2660 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2663 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2665 case ISD::AND: return getConstant(C1 & C2, VT);
2666 case ISD::OR: return getConstant(C1 | C2, VT);
2667 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2668 case ISD::SHL: return getConstant(C1 << C2, VT);
2669 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2670 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2671 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2672 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2679 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2680 SDValue N1, SDValue N2) {
2681 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2682 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2685 case ISD::TokenFactor:
2686 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2687 N2.getValueType() == MVT::Other && "Invalid token factor!");
2688 // Fold trivial token factors.
2689 if (N1.getOpcode() == ISD::EntryToken) return N2;
2690 if (N2.getOpcode() == ISD::EntryToken) return N1;
2691 if (N1 == N2) return N1;
2693 case ISD::CONCAT_VECTORS:
2694 // Concat of UNDEFs is UNDEF.
2695 if (N1.getOpcode() == ISD::UNDEF &&
2696 N2.getOpcode() == ISD::UNDEF)
2697 return getUNDEF(VT);
2699 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2700 // one big BUILD_VECTOR.
2701 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2702 N2.getOpcode() == ISD::BUILD_VECTOR) {
2703 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2704 N1.getNode()->op_end());
2705 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2706 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2710 assert(VT.isInteger() && "This operator does not apply to FP types!");
2711 assert(N1.getValueType() == N2.getValueType() &&
2712 N1.getValueType() == VT && "Binary operator types must match!");
2713 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2714 // worth handling here.
2715 if (N2C && N2C->isNullValue())
2717 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2724 assert(VT.isInteger() && "This operator does not apply to FP types!");
2725 assert(N1.getValueType() == N2.getValueType() &&
2726 N1.getValueType() == VT && "Binary operator types must match!");
2727 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2728 // it's worth handling here.
2729 if (N2C && N2C->isNullValue())
2739 assert(VT.isInteger() && "This operator does not apply to FP types!");
2740 assert(N1.getValueType() == N2.getValueType() &&
2741 N1.getValueType() == VT && "Binary operator types must match!");
2748 if (getTarget().Options.UnsafeFPMath) {
2749 if (Opcode == ISD::FADD) {
2751 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2752 if (CFP->getValueAPF().isZero())
2755 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2756 if (CFP->getValueAPF().isZero())
2758 } else if (Opcode == ISD::FSUB) {
2760 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2761 if (CFP->getValueAPF().isZero())
2765 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2766 assert(N1.getValueType() == N2.getValueType() &&
2767 N1.getValueType() == VT && "Binary operator types must match!");
2769 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2770 assert(N1.getValueType() == VT &&
2771 N1.getValueType().isFloatingPoint() &&
2772 N2.getValueType().isFloatingPoint() &&
2773 "Invalid FCOPYSIGN!");
2780 assert(VT == N1.getValueType() &&
2781 "Shift operators return type must be the same as their first arg");
2782 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2783 "Shifts only work on integers");
2784 // Verify that the shift amount VT is bit enough to hold valid shift
2785 // amounts. This catches things like trying to shift an i1024 value by an
2786 // i8, which is easy to fall into in generic code that uses
2787 // TLI.getShiftAmount().
2788 assert(N2.getValueType().getSizeInBits() >=
2789 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2790 "Invalid use of small shift amount with oversized value!");
2792 // Always fold shifts of i1 values so the code generator doesn't need to
2793 // handle them. Since we know the size of the shift has to be less than the
2794 // size of the value, the shift/rotate count is guaranteed to be zero.
2797 if (N2C && N2C->isNullValue())
2800 case ISD::FP_ROUND_INREG: {
2801 EVT EVT = cast<VTSDNode>(N2)->getVT();
2802 assert(VT == N1.getValueType() && "Not an inreg round!");
2803 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2804 "Cannot FP_ROUND_INREG integer types");
2805 assert(EVT.isVector() == VT.isVector() &&
2806 "FP_ROUND_INREG type should be vector iff the operand "
2808 assert((!EVT.isVector() ||
2809 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2810 "Vector element counts must match in FP_ROUND_INREG");
2811 assert(EVT.bitsLE(VT) && "Not rounding down!");
2813 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2817 assert(VT.isFloatingPoint() &&
2818 N1.getValueType().isFloatingPoint() &&
2819 VT.bitsLE(N1.getValueType()) &&
2820 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2821 if (N1.getValueType() == VT) return N1; // noop conversion.
2823 case ISD::AssertSext:
2824 case ISD::AssertZext: {
2825 EVT EVT = cast<VTSDNode>(N2)->getVT();
2826 assert(VT == N1.getValueType() && "Not an inreg extend!");
2827 assert(VT.isInteger() && EVT.isInteger() &&
2828 "Cannot *_EXTEND_INREG FP types");
2829 assert(!EVT.isVector() &&
2830 "AssertSExt/AssertZExt type should be the vector element type "
2831 "rather than the vector type!");
2832 assert(EVT.bitsLE(VT) && "Not extending!");
2833 if (VT == EVT) return N1; // noop assertion.
2836 case ISD::SIGN_EXTEND_INREG: {
2837 EVT EVT = cast<VTSDNode>(N2)->getVT();
2838 assert(VT == N1.getValueType() && "Not an inreg extend!");
2839 assert(VT.isInteger() && EVT.isInteger() &&
2840 "Cannot *_EXTEND_INREG FP types");
2841 assert(EVT.isVector() == VT.isVector() &&
2842 "SIGN_EXTEND_INREG type should be vector iff the operand "
2844 assert((!EVT.isVector() ||
2845 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2846 "Vector element counts must match in SIGN_EXTEND_INREG");
2847 assert(EVT.bitsLE(VT) && "Not extending!");
2848 if (EVT == VT) return N1; // Not actually extending
2851 APInt Val = N1C->getAPIntValue();
2852 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2853 Val <<= Val.getBitWidth()-FromBits;
2854 Val = Val.ashr(Val.getBitWidth()-FromBits);
2855 return getConstant(Val, VT);
2859 case ISD::EXTRACT_VECTOR_ELT:
2860 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2861 if (N1.getOpcode() == ISD::UNDEF)
2862 return getUNDEF(VT);
2864 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2865 // expanding copies of large vectors from registers.
2867 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2868 N1.getNumOperands() > 0) {
2870 N1.getOperand(0).getValueType().getVectorNumElements();
2871 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2872 N1.getOperand(N2C->getZExtValue() / Factor),
2873 getConstant(N2C->getZExtValue() % Factor,
2874 N2.getValueType()));
2877 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2878 // expanding large vector constants.
2879 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2880 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2881 EVT VEltTy = N1.getValueType().getVectorElementType();
2882 if (Elt.getValueType() != VEltTy) {
2883 // If the vector element type is not legal, the BUILD_VECTOR operands
2884 // are promoted and implicitly truncated. Make that explicit here.
2885 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt);
2888 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT
2889 // result is implicitly extended.
2890 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt);
2895 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2896 // operations are lowered to scalars.
2897 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2898 // If the indices are the same, return the inserted element else
2899 // if the indices are known different, extract the element from
2900 // the original vector.
2901 SDValue N1Op2 = N1.getOperand(2);
2902 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2904 if (N1Op2C && N2C) {
2905 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2906 if (VT == N1.getOperand(1).getValueType())
2907 return N1.getOperand(1);
2909 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2912 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2916 case ISD::EXTRACT_ELEMENT:
2917 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2918 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2919 (N1.getValueType().isInteger() == VT.isInteger()) &&
2920 N1.getValueType() != VT &&
2921 "Wrong types for EXTRACT_ELEMENT!");
2923 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2924 // 64-bit integers into 32-bit parts. Instead of building the extract of
2925 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2926 if (N1.getOpcode() == ISD::BUILD_PAIR)
2927 return N1.getOperand(N2C->getZExtValue());
2929 // EXTRACT_ELEMENT of a constant int is also very common.
2930 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2931 unsigned ElementSize = VT.getSizeInBits();
2932 unsigned Shift = ElementSize * N2C->getZExtValue();
2933 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2934 return getConstant(ShiftedVal.trunc(ElementSize), VT);
2937 case ISD::EXTRACT_SUBVECTOR: {
2939 if (VT.isSimple() && N1.getValueType().isSimple()) {
2940 assert(VT.isVector() && N1.getValueType().isVector() &&
2941 "Extract subvector VTs must be a vectors!");
2942 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
2943 "Extract subvector VTs must have the same element type!");
2944 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
2945 "Extract subvector must be from larger vector to smaller vector!");
2947 if (isa<ConstantSDNode>(Index.getNode())) {
2948 assert((VT.getVectorNumElements() +
2949 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
2950 <= N1.getValueType().getVectorNumElements())
2951 && "Extract subvector overflow!");
2954 // Trivial extraction.
2955 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
2964 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
2965 if (SV.getNode()) return SV;
2966 } else { // Cannonicalize constant to RHS if commutative
2967 if (isCommutativeBinOp(Opcode)) {
2968 std::swap(N1C, N2C);
2974 // Constant fold FP operations.
2975 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
2976 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
2978 if (!N2CFP && isCommutativeBinOp(Opcode)) {
2979 // Cannonicalize constant to RHS if commutative
2980 std::swap(N1CFP, N2CFP);
2982 } else if (N2CFP && VT != MVT::ppcf128) {
2983 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2984 APFloat::opStatus s;
2987 s = V1.add(V2, APFloat::rmNearestTiesToEven);
2988 if (s != APFloat::opInvalidOp)
2989 return getConstantFP(V1, VT);
2992 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2993 if (s!=APFloat::opInvalidOp)
2994 return getConstantFP(V1, VT);
2997 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2998 if (s!=APFloat::opInvalidOp)
2999 return getConstantFP(V1, VT);
3002 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3003 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3004 return getConstantFP(V1, VT);
3007 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3008 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3009 return getConstantFP(V1, VT);
3011 case ISD::FCOPYSIGN:
3013 return getConstantFP(V1, VT);
3018 if (Opcode == ISD::FP_ROUND) {
3019 APFloat V = N1CFP->getValueAPF(); // make copy
3021 // This can return overflow, underflow, or inexact; we don't care.
3022 // FIXME need to be more flexible about rounding mode.
3023 (void)V.convert(*EVTToAPFloatSemantics(VT),
3024 APFloat::rmNearestTiesToEven, &ignored);
3025 return getConstantFP(V, VT);
3029 // Canonicalize an UNDEF to the RHS, even over a constant.
3030 if (N1.getOpcode() == ISD::UNDEF) {
3031 if (isCommutativeBinOp(Opcode)) {
3035 case ISD::FP_ROUND_INREG:
3036 case ISD::SIGN_EXTEND_INREG:
3042 return N1; // fold op(undef, arg2) -> undef
3050 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3051 // For vectors, we can't easily build an all zero vector, just return
3058 // Fold a bunch of operators when the RHS is undef.
3059 if (N2.getOpcode() == ISD::UNDEF) {
3062 if (N1.getOpcode() == ISD::UNDEF)
3063 // Handle undef ^ undef -> 0 special case. This is a common
3065 return getConstant(0, VT);
3075 return N2; // fold op(arg1, undef) -> undef
3081 if (getTarget().Options.UnsafeFPMath)
3089 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3090 // For vectors, we can't easily build an all zero vector, just return
3095 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3096 // For vectors, we can't easily build an all one vector, just return
3104 // Memoize this node if possible.
3106 SDVTList VTs = getVTList(VT);
3107 if (VT != MVT::Glue) {
3108 SDValue Ops[] = { N1, N2 };
3109 FoldingSetNodeID ID;
3110 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3112 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3113 return SDValue(E, 0);
3115 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3116 CSEMap.InsertNode(N, IP);
3118 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3121 AllNodes.push_back(N);
3125 return SDValue(N, 0);
3128 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3129 SDValue N1, SDValue N2, SDValue N3) {
3130 // Perform various simplifications.
3131 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3133 case ISD::CONCAT_VECTORS:
3134 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3135 // one big BUILD_VECTOR.
3136 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3137 N2.getOpcode() == ISD::BUILD_VECTOR &&
3138 N3.getOpcode() == ISD::BUILD_VECTOR) {
3139 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3140 N1.getNode()->op_end());
3141 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3142 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3143 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3147 // Use FoldSetCC to simplify SETCC's.
3148 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3149 if (Simp.getNode()) return Simp;
3154 if (N1C->getZExtValue())
3155 return N2; // select true, X, Y -> X
3156 return N3; // select false, X, Y -> Y
3159 if (N2 == N3) return N2; // select C, X, X -> X
3161 case ISD::VECTOR_SHUFFLE:
3162 llvm_unreachable("should use getVectorShuffle constructor!");
3163 case ISD::INSERT_SUBVECTOR: {
3165 if (VT.isSimple() && N1.getValueType().isSimple()
3166 && N2.getValueType().isSimple()) {
3167 assert(VT.isVector() && N1.getValueType().isVector() &&
3168 N2.getValueType().isVector() &&
3169 "Insert subvector VTs must be a vectors");
3170 assert(VT == N1.getValueType() &&
3171 "Dest and insert subvector source types must match!");
3172 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3173 "Insert subvector must be from smaller vector to larger vector!");
3174 if (isa<ConstantSDNode>(Index.getNode())) {
3175 assert((N2.getValueType().getVectorNumElements() +
3176 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3177 <= VT.getVectorNumElements())
3178 && "Insert subvector overflow!");
3181 // Trivial insertion.
3182 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3188 // Fold bit_convert nodes from a type to themselves.
3189 if (N1.getValueType() == VT)
3194 // Memoize node if it doesn't produce a flag.
3196 SDVTList VTs = getVTList(VT);
3197 if (VT != MVT::Glue) {
3198 SDValue Ops[] = { N1, N2, N3 };
3199 FoldingSetNodeID ID;
3200 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3202 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3203 return SDValue(E, 0);
3205 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3206 CSEMap.InsertNode(N, IP);
3208 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3211 AllNodes.push_back(N);
3215 return SDValue(N, 0);
3218 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3219 SDValue N1, SDValue N2, SDValue N3,
3221 SDValue Ops[] = { N1, N2, N3, N4 };
3222 return getNode(Opcode, DL, VT, Ops, 4);
3225 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3226 SDValue N1, SDValue N2, SDValue N3,
3227 SDValue N4, SDValue N5) {
3228 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3229 return getNode(Opcode, DL, VT, Ops, 5);
3232 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3233 /// the incoming stack arguments to be loaded from the stack.
3234 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3235 SmallVector<SDValue, 8> ArgChains;
3237 // Include the original chain at the beginning of the list. When this is
3238 // used by target LowerCall hooks, this helps legalize find the
3239 // CALLSEQ_BEGIN node.
3240 ArgChains.push_back(Chain);
3242 // Add a chain value for each stack argument.
3243 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3244 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3245 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3246 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3247 if (FI->getIndex() < 0)
3248 ArgChains.push_back(SDValue(L, 1));
3250 // Build a tokenfactor for all the chains.
3251 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3252 &ArgChains[0], ArgChains.size());
3255 /// SplatByte - Distribute ByteVal over NumBits bits.
3256 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3257 APInt Val = APInt(NumBits, ByteVal);
3259 for (unsigned i = NumBits; i > 8; i >>= 1) {
3260 Val = (Val << Shift) | Val;
3266 /// getMemsetValue - Vectorized representation of the memset value
3268 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3270 assert(Value.getOpcode() != ISD::UNDEF);
3272 unsigned NumBits = VT.getScalarType().getSizeInBits();
3273 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3274 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3276 return DAG.getConstant(Val, VT);
3277 return DAG.getConstantFP(APFloat(Val), VT);
3280 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3282 // Use a multiplication with 0x010101... to extend the input to the
3284 APInt Magic = SplatByte(NumBits, 0x01);
3285 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3291 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3292 /// used when a memcpy is turned into a memset when the source is a constant
3294 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3295 const TargetLowering &TLI, StringRef Str) {
3296 // Handle vector with all elements zero.
3299 return DAG.getConstant(0, VT);
3300 else if (VT == MVT::f32 || VT == MVT::f64)
3301 return DAG.getConstantFP(0.0, VT);
3302 else if (VT.isVector()) {
3303 unsigned NumElts = VT.getVectorNumElements();
3304 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3305 return DAG.getNode(ISD::BITCAST, dl, VT,
3306 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3309 llvm_unreachable("Expected type!");
3312 assert(!VT.isVector() && "Can't handle vector type here!");
3313 unsigned NumVTBytes = VT.getSizeInBits() / 8;
3314 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3317 if (TLI.isLittleEndian()) {
3318 for (unsigned i = 0; i != NumBytes; ++i)
3319 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3321 for (unsigned i = 0; i != NumBytes; ++i)
3322 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3325 return DAG.getConstant(Val, VT);
3328 /// getMemBasePlusOffset - Returns base and offset node for the
3330 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3331 SelectionDAG &DAG) {
3332 EVT VT = Base.getValueType();
3333 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3334 VT, Base, DAG.getConstant(Offset, VT));
3337 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3339 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3340 unsigned SrcDelta = 0;
3341 GlobalAddressSDNode *G = NULL;
3342 if (Src.getOpcode() == ISD::GlobalAddress)
3343 G = cast<GlobalAddressSDNode>(Src);
3344 else if (Src.getOpcode() == ISD::ADD &&
3345 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3346 Src.getOperand(1).getOpcode() == ISD::Constant) {
3347 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3348 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3353 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3356 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3357 /// to replace the memset / memcpy. Return true if the number of memory ops
3358 /// is below the threshold. It returns the types of the sequence of
3359 /// memory ops to perform memset / memcpy by reference.
3360 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3361 unsigned Limit, uint64_t Size,
3362 unsigned DstAlign, unsigned SrcAlign,
3366 const TargetLowering &TLI) {
3367 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3368 "Expecting memcpy / memset source to meet alignment requirement!");
3369 // If 'SrcAlign' is zero, that means the memory operation does not need to
3370 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3371 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3372 // is the specified alignment of the memory operation. If it is zero, that
3373 // means it's possible to change the alignment of the destination.
3374 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3375 // not need to be loaded.
3376 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3377 IsZeroVal, MemcpyStrSrc,
3378 DAG.getMachineFunction());
3380 if (VT == MVT::Other) {
3381 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3382 TLI.allowsUnalignedMemoryAccesses(VT)) {
3383 VT = TLI.getPointerTy();
3385 switch (DstAlign & 7) {
3386 case 0: VT = MVT::i64; break;
3387 case 4: VT = MVT::i32; break;
3388 case 2: VT = MVT::i16; break;
3389 default: VT = MVT::i8; break;
3394 while (!TLI.isTypeLegal(LVT))
3395 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3396 assert(LVT.isInteger());
3402 unsigned NumMemOps = 0;
3404 unsigned VTSize = VT.getSizeInBits() / 8;
3405 while (VTSize > Size) {
3406 // For now, only use non-vector load / store's for the left-over pieces.
3407 if (VT.isVector() || VT.isFloatingPoint()) {
3409 while (!TLI.isTypeLegal(VT))
3410 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3411 VTSize = VT.getSizeInBits() / 8;
3413 // This can result in a type that is not legal on the target, e.g.
3414 // 1 or 2 bytes on PPC.
3415 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3420 if (++NumMemOps > Limit)
3422 MemOps.push_back(VT);
3429 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3430 SDValue Chain, SDValue Dst,
3431 SDValue Src, uint64_t Size,
3432 unsigned Align, bool isVol,
3434 MachinePointerInfo DstPtrInfo,
3435 MachinePointerInfo SrcPtrInfo) {
3436 // Turn a memcpy of undef to nop.
3437 if (Src.getOpcode() == ISD::UNDEF)
3440 // Expand memcpy to a series of load and store ops if the size operand falls
3441 // below a certain threshold.
3442 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3443 // rather than maybe a humongous number of loads and stores.
3444 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3445 std::vector<EVT> MemOps;
3446 bool DstAlignCanChange = false;
3447 MachineFunction &MF = DAG.getMachineFunction();
3448 MachineFrameInfo *MFI = MF.getFrameInfo();
3449 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3450 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3451 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3452 DstAlignCanChange = true;
3453 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3454 if (Align > SrcAlign)
3457 bool CopyFromStr = isMemSrcFromString(Src, Str);
3458 bool isZeroStr = CopyFromStr && Str.empty();
3459 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3461 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3462 (DstAlignCanChange ? 0 : Align),
3463 (isZeroStr ? 0 : SrcAlign),
3464 true, CopyFromStr, DAG, TLI))
3467 if (DstAlignCanChange) {
3468 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3469 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3470 if (NewAlign > Align) {
3471 // Give the stack frame object a larger alignment if needed.
3472 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3473 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3478 SmallVector<SDValue, 8> OutChains;
3479 unsigned NumMemOps = MemOps.size();
3480 uint64_t SrcOff = 0, DstOff = 0;
3481 for (unsigned i = 0; i != NumMemOps; ++i) {
3483 unsigned VTSize = VT.getSizeInBits() / 8;
3484 SDValue Value, Store;
3487 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3488 // It's unlikely a store of a vector immediate can be done in a single
3489 // instruction. It would require a load from a constantpool first.
3490 // We only handle zero vectors here.
3491 // FIXME: Handle other cases where store of vector immediate is done in
3492 // a single instruction.
3493 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3494 Store = DAG.getStore(Chain, dl, Value,
3495 getMemBasePlusOffset(Dst, DstOff, DAG),
3496 DstPtrInfo.getWithOffset(DstOff), isVol,
3499 // The type might not be legal for the target. This should only happen
3500 // if the type is smaller than a legal type, as on PPC, so the right
3501 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3502 // to Load/Store if NVT==VT.
3503 // FIXME does the case above also need this?
3504 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3505 assert(NVT.bitsGE(VT));
3506 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3507 getMemBasePlusOffset(Src, SrcOff, DAG),
3508 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3509 MinAlign(SrcAlign, SrcOff));
3510 Store = DAG.getTruncStore(Chain, dl, Value,
3511 getMemBasePlusOffset(Dst, DstOff, DAG),
3512 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3515 OutChains.push_back(Store);
3520 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3521 &OutChains[0], OutChains.size());
3524 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3525 SDValue Chain, SDValue Dst,
3526 SDValue Src, uint64_t Size,
3527 unsigned Align, bool isVol,
3529 MachinePointerInfo DstPtrInfo,
3530 MachinePointerInfo SrcPtrInfo) {
3531 // Turn a memmove of undef to nop.
3532 if (Src.getOpcode() == ISD::UNDEF)
3535 // Expand memmove to a series of load and store ops if the size operand falls
3536 // below a certain threshold.
3537 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3538 std::vector<EVT> MemOps;
3539 bool DstAlignCanChange = false;
3540 MachineFunction &MF = DAG.getMachineFunction();
3541 MachineFrameInfo *MFI = MF.getFrameInfo();
3542 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3543 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3544 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3545 DstAlignCanChange = true;
3546 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3547 if (Align > SrcAlign)
3549 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3551 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3552 (DstAlignCanChange ? 0 : Align),
3553 SrcAlign, true, false, DAG, TLI))
3556 if (DstAlignCanChange) {
3557 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3558 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3559 if (NewAlign > Align) {
3560 // Give the stack frame object a larger alignment if needed.
3561 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3562 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3567 uint64_t SrcOff = 0, DstOff = 0;
3568 SmallVector<SDValue, 8> LoadValues;
3569 SmallVector<SDValue, 8> LoadChains;
3570 SmallVector<SDValue, 8> OutChains;
3571 unsigned NumMemOps = MemOps.size();
3572 for (unsigned i = 0; i < NumMemOps; i++) {
3574 unsigned VTSize = VT.getSizeInBits() / 8;
3575 SDValue Value, Store;
3577 Value = DAG.getLoad(VT, dl, Chain,
3578 getMemBasePlusOffset(Src, SrcOff, DAG),
3579 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3580 false, false, SrcAlign);
3581 LoadValues.push_back(Value);
3582 LoadChains.push_back(Value.getValue(1));
3585 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3586 &LoadChains[0], LoadChains.size());
3588 for (unsigned i = 0; i < NumMemOps; i++) {
3590 unsigned VTSize = VT.getSizeInBits() / 8;
3591 SDValue Value, Store;
3593 Store = DAG.getStore(Chain, dl, LoadValues[i],
3594 getMemBasePlusOffset(Dst, DstOff, DAG),
3595 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3596 OutChains.push_back(Store);
3600 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3601 &OutChains[0], OutChains.size());
3604 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3605 SDValue Chain, SDValue Dst,
3606 SDValue Src, uint64_t Size,
3607 unsigned Align, bool isVol,
3608 MachinePointerInfo DstPtrInfo) {
3609 // Turn a memset of undef to nop.
3610 if (Src.getOpcode() == ISD::UNDEF)
3613 // Expand memset to a series of load/store ops if the size operand
3614 // falls below a certain threshold.
3615 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3616 std::vector<EVT> MemOps;
3617 bool DstAlignCanChange = false;
3618 MachineFunction &MF = DAG.getMachineFunction();
3619 MachineFrameInfo *MFI = MF.getFrameInfo();
3620 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3621 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3622 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3623 DstAlignCanChange = true;
3625 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3626 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3627 Size, (DstAlignCanChange ? 0 : Align), 0,
3628 IsZeroVal, false, DAG, TLI))
3631 if (DstAlignCanChange) {
3632 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3633 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3634 if (NewAlign > Align) {
3635 // Give the stack frame object a larger alignment if needed.
3636 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3637 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3642 SmallVector<SDValue, 8> OutChains;
3643 uint64_t DstOff = 0;
3644 unsigned NumMemOps = MemOps.size();
3646 // Find the largest store and generate the bit pattern for it.
3647 EVT LargestVT = MemOps[0];
3648 for (unsigned i = 1; i < NumMemOps; i++)
3649 if (MemOps[i].bitsGT(LargestVT))
3650 LargestVT = MemOps[i];
3651 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3653 for (unsigned i = 0; i < NumMemOps; i++) {
3656 // If this store is smaller than the largest store see whether we can get
3657 // the smaller value for free with a truncate.
3658 SDValue Value = MemSetValue;
3659 if (VT.bitsLT(LargestVT)) {
3660 if (!LargestVT.isVector() && !VT.isVector() &&
3661 TLI.isTruncateFree(LargestVT, VT))
3662 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3664 Value = getMemsetValue(Src, VT, DAG, dl);
3666 assert(Value.getValueType() == VT && "Value with wrong type.");
3667 SDValue Store = DAG.getStore(Chain, dl, Value,
3668 getMemBasePlusOffset(Dst, DstOff, DAG),
3669 DstPtrInfo.getWithOffset(DstOff),
3670 isVol, false, Align);
3671 OutChains.push_back(Store);
3672 DstOff += VT.getSizeInBits() / 8;
3675 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3676 &OutChains[0], OutChains.size());
3679 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3680 SDValue Src, SDValue Size,
3681 unsigned Align, bool isVol, bool AlwaysInline,
3682 MachinePointerInfo DstPtrInfo,
3683 MachinePointerInfo SrcPtrInfo) {
3685 // Check to see if we should lower the memcpy to loads and stores first.
3686 // For cases within the target-specified limits, this is the best choice.
3687 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3689 // Memcpy with size zero? Just return the original chain.
3690 if (ConstantSize->isNullValue())
3693 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3694 ConstantSize->getZExtValue(),Align,
3695 isVol, false, DstPtrInfo, SrcPtrInfo);
3696 if (Result.getNode())
3700 // Then check to see if we should lower the memcpy with target-specific
3701 // code. If the target chooses to do this, this is the next best.
3703 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3704 isVol, AlwaysInline,
3705 DstPtrInfo, SrcPtrInfo);
3706 if (Result.getNode())
3709 // If we really need inline code and the target declined to provide it,
3710 // use a (potentially long) sequence of loads and stores.
3712 assert(ConstantSize && "AlwaysInline requires a constant size!");
3713 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3714 ConstantSize->getZExtValue(), Align, isVol,
3715 true, DstPtrInfo, SrcPtrInfo);
3718 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3719 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3720 // respect volatile, so they may do things like read or write memory
3721 // beyond the given memory regions. But fixing this isn't easy, and most
3722 // people don't care.
3724 // Emit a library call.
3725 TargetLowering::ArgListTy Args;
3726 TargetLowering::ArgListEntry Entry;
3727 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3728 Entry.Node = Dst; Args.push_back(Entry);
3729 Entry.Node = Src; Args.push_back(Entry);
3730 Entry.Node = Size; Args.push_back(Entry);
3731 // FIXME: pass in DebugLoc
3733 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3734 false, false, false, false, 0,
3735 TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3736 /*isTailCall=*/false,
3737 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3738 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3739 TLI.getPointerTy()),
3741 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3743 return CallResult.second;
3746 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3747 SDValue Src, SDValue Size,
3748 unsigned Align, bool isVol,
3749 MachinePointerInfo DstPtrInfo,
3750 MachinePointerInfo SrcPtrInfo) {
3752 // Check to see if we should lower the memmove to loads and stores first.
3753 // For cases within the target-specified limits, this is the best choice.
3754 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3756 // Memmove with size zero? Just return the original chain.
3757 if (ConstantSize->isNullValue())
3761 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3762 ConstantSize->getZExtValue(), Align, isVol,
3763 false, DstPtrInfo, SrcPtrInfo);
3764 if (Result.getNode())
3768 // Then check to see if we should lower the memmove with target-specific
3769 // code. If the target chooses to do this, this is the next best.
3771 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3772 DstPtrInfo, SrcPtrInfo);
3773 if (Result.getNode())
3776 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3777 // not be safe. See memcpy above for more details.
3779 // Emit a library call.
3780 TargetLowering::ArgListTy Args;
3781 TargetLowering::ArgListEntry Entry;
3782 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3783 Entry.Node = Dst; Args.push_back(Entry);
3784 Entry.Node = Src; Args.push_back(Entry);
3785 Entry.Node = Size; Args.push_back(Entry);
3786 // FIXME: pass in DebugLoc
3788 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3789 false, false, false, false, 0,
3790 TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3791 /*isTailCall=*/false,
3792 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3793 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3794 TLI.getPointerTy()),
3796 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3798 return CallResult.second;
3801 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3802 SDValue Src, SDValue Size,
3803 unsigned Align, bool isVol,
3804 MachinePointerInfo DstPtrInfo) {
3806 // Check to see if we should lower the memset to stores first.
3807 // For cases within the target-specified limits, this is the best choice.
3808 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3810 // Memset with size zero? Just return the original chain.
3811 if (ConstantSize->isNullValue())
3815 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3816 Align, isVol, DstPtrInfo);
3818 if (Result.getNode())
3822 // Then check to see if we should lower the memset with target-specific
3823 // code. If the target chooses to do this, this is the next best.
3825 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3827 if (Result.getNode())
3830 // Emit a library call.
3831 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3832 TargetLowering::ArgListTy Args;
3833 TargetLowering::ArgListEntry Entry;
3834 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3835 Args.push_back(Entry);
3836 // Extend or truncate the argument to be an i32 value for the call.
3837 if (Src.getValueType().bitsGT(MVT::i32))
3838 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3840 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3842 Entry.Ty = Type::getInt32Ty(*getContext());
3843 Entry.isSExt = true;
3844 Args.push_back(Entry);
3846 Entry.Ty = IntPtrTy;
3847 Entry.isSExt = false;
3848 Args.push_back(Entry);
3849 // FIXME: pass in DebugLoc
3851 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3852 false, false, false, false, 0,
3853 TLI.getLibcallCallingConv(RTLIB::MEMSET),
3854 /*isTailCall=*/false,
3855 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3856 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3857 TLI.getPointerTy()),
3859 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3861 return CallResult.second;
3864 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3865 SDValue Chain, SDValue Ptr, SDValue Cmp,
3866 SDValue Swp, MachinePointerInfo PtrInfo,
3868 AtomicOrdering Ordering,
3869 SynchronizationScope SynchScope) {
3870 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3871 Alignment = getEVTAlignment(MemVT);
3873 MachineFunction &MF = getMachineFunction();
3874 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
3876 // For now, atomics are considered to be volatile always.
3877 // FIXME: Volatile isn't really correct; we should keep track of atomic
3878 // orderings in the memoperand.
3879 Flags |= MachineMemOperand::MOVolatile;
3881 MachineMemOperand *MMO =
3882 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3884 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3885 Ordering, SynchScope);
3888 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3890 SDValue Ptr, SDValue Cmp,
3891 SDValue Swp, MachineMemOperand *MMO,
3892 AtomicOrdering Ordering,
3893 SynchronizationScope SynchScope) {
3894 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3895 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3897 EVT VT = Cmp.getValueType();
3899 SDVTList VTs = getVTList(VT, MVT::Other);
3900 FoldingSetNodeID ID;
3901 ID.AddInteger(MemVT.getRawBits());
3902 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3903 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3905 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3906 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3907 return SDValue(E, 0);
3909 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3910 Ptr, Cmp, Swp, MMO, Ordering,
3912 CSEMap.InsertNode(N, IP);
3913 AllNodes.push_back(N);
3914 return SDValue(N, 0);
3917 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3919 SDValue Ptr, SDValue Val,
3920 const Value* PtrVal,
3922 AtomicOrdering Ordering,
3923 SynchronizationScope SynchScope) {
3924 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3925 Alignment = getEVTAlignment(MemVT);
3927 MachineFunction &MF = getMachineFunction();
3928 // A monotonic store does not load; a release store "loads" in the sense
3929 // that other stores cannot be sunk past it.
3930 // (An atomicrmw obviously both loads and stores.)
3931 unsigned Flags = MachineMemOperand::MOStore;
3932 if (Opcode != ISD::ATOMIC_STORE || Ordering > Monotonic)
3933 Flags |= MachineMemOperand::MOLoad;
3935 // For now, atomics are considered to be volatile always.
3936 // FIXME: Volatile isn't really correct; we should keep track of atomic
3937 // orderings in the memoperand.
3938 Flags |= MachineMemOperand::MOVolatile;
3940 MachineMemOperand *MMO =
3941 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
3942 MemVT.getStoreSize(), Alignment);
3944 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
3945 Ordering, SynchScope);
3948 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3950 SDValue Ptr, SDValue Val,
3951 MachineMemOperand *MMO,
3952 AtomicOrdering Ordering,
3953 SynchronizationScope SynchScope) {
3954 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
3955 Opcode == ISD::ATOMIC_LOAD_SUB ||
3956 Opcode == ISD::ATOMIC_LOAD_AND ||
3957 Opcode == ISD::ATOMIC_LOAD_OR ||
3958 Opcode == ISD::ATOMIC_LOAD_XOR ||
3959 Opcode == ISD::ATOMIC_LOAD_NAND ||
3960 Opcode == ISD::ATOMIC_LOAD_MIN ||
3961 Opcode == ISD::ATOMIC_LOAD_MAX ||
3962 Opcode == ISD::ATOMIC_LOAD_UMIN ||
3963 Opcode == ISD::ATOMIC_LOAD_UMAX ||
3964 Opcode == ISD::ATOMIC_SWAP ||
3965 Opcode == ISD::ATOMIC_STORE) &&
3966 "Invalid Atomic Op");
3968 EVT VT = Val.getValueType();
3970 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
3971 getVTList(VT, MVT::Other);
3972 FoldingSetNodeID ID;
3973 ID.AddInteger(MemVT.getRawBits());
3974 SDValue Ops[] = {Chain, Ptr, Val};
3975 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3977 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3978 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3979 return SDValue(E, 0);
3981 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3983 Ordering, SynchScope);
3984 CSEMap.InsertNode(N, IP);
3985 AllNodes.push_back(N);
3986 return SDValue(N, 0);
3989 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3990 EVT VT, SDValue Chain,
3992 const Value* PtrVal,
3994 AtomicOrdering Ordering,
3995 SynchronizationScope SynchScope) {
3996 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3997 Alignment = getEVTAlignment(MemVT);
3999 MachineFunction &MF = getMachineFunction();
4000 // A monotonic load does not store; an acquire load "stores" in the sense
4001 // that other loads cannot be hoisted past it.
4002 unsigned Flags = MachineMemOperand::MOLoad;
4003 if (Ordering > Monotonic)
4004 Flags |= MachineMemOperand::MOStore;
4006 // For now, atomics are considered to be volatile always.
4007 // FIXME: Volatile isn't really correct; we should keep track of atomic
4008 // orderings in the memoperand.
4009 Flags |= MachineMemOperand::MOVolatile;
4011 MachineMemOperand *MMO =
4012 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4013 MemVT.getStoreSize(), Alignment);
4015 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4016 Ordering, SynchScope);
4019 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4020 EVT VT, SDValue Chain,
4022 MachineMemOperand *MMO,
4023 AtomicOrdering Ordering,
4024 SynchronizationScope SynchScope) {
4025 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4027 SDVTList VTs = getVTList(VT, MVT::Other);
4028 FoldingSetNodeID ID;
4029 ID.AddInteger(MemVT.getRawBits());
4030 SDValue Ops[] = {Chain, Ptr};
4031 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4033 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4034 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4035 return SDValue(E, 0);
4037 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4038 Ptr, MMO, Ordering, SynchScope);
4039 CSEMap.InsertNode(N, IP);
4040 AllNodes.push_back(N);
4041 return SDValue(N, 0);
4044 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4045 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4050 SmallVector<EVT, 4> VTs;
4051 VTs.reserve(NumOps);
4052 for (unsigned i = 0; i < NumOps; ++i)
4053 VTs.push_back(Ops[i].getValueType());
4054 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4059 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4060 const EVT *VTs, unsigned NumVTs,
4061 const SDValue *Ops, unsigned NumOps,
4062 EVT MemVT, MachinePointerInfo PtrInfo,
4063 unsigned Align, bool Vol,
4064 bool ReadMem, bool WriteMem) {
4065 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4066 MemVT, PtrInfo, Align, Vol,
4071 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4072 const SDValue *Ops, unsigned NumOps,
4073 EVT MemVT, MachinePointerInfo PtrInfo,
4074 unsigned Align, bool Vol,
4075 bool ReadMem, bool WriteMem) {
4076 if (Align == 0) // Ensure that codegen never sees alignment 0
4077 Align = getEVTAlignment(MemVT);
4079 MachineFunction &MF = getMachineFunction();
4082 Flags |= MachineMemOperand::MOStore;
4084 Flags |= MachineMemOperand::MOLoad;
4086 Flags |= MachineMemOperand::MOVolatile;
4087 MachineMemOperand *MMO =
4088 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4090 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4094 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4095 const SDValue *Ops, unsigned NumOps,
4096 EVT MemVT, MachineMemOperand *MMO) {
4097 assert((Opcode == ISD::INTRINSIC_VOID ||
4098 Opcode == ISD::INTRINSIC_W_CHAIN ||
4099 Opcode == ISD::PREFETCH ||
4100 (Opcode <= INT_MAX &&
4101 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4102 "Opcode is not a memory-accessing opcode!");
4104 // Memoize the node unless it returns a flag.
4105 MemIntrinsicSDNode *N;
4106 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4107 FoldingSetNodeID ID;
4108 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4110 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4111 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4112 return SDValue(E, 0);
4115 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4117 CSEMap.InsertNode(N, IP);
4119 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4122 AllNodes.push_back(N);
4123 return SDValue(N, 0);
4126 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4127 /// MachinePointerInfo record from it. This is particularly useful because the
4128 /// code generator has many cases where it doesn't bother passing in a
4129 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4130 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4131 // If this is FI+Offset, we can model it.
4132 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4133 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4135 // If this is (FI+Offset1)+Offset2, we can model it.
4136 if (Ptr.getOpcode() != ISD::ADD ||
4137 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4138 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4139 return MachinePointerInfo();
4141 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4142 return MachinePointerInfo::getFixedStack(FI, Offset+
4143 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4146 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4147 /// MachinePointerInfo record from it. This is particularly useful because the
4148 /// code generator has many cases where it doesn't bother passing in a
4149 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4150 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4151 // If the 'Offset' value isn't a constant, we can't handle this.
4152 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4153 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4154 if (OffsetOp.getOpcode() == ISD::UNDEF)
4155 return InferPointerInfo(Ptr);
4156 return MachinePointerInfo();
4161 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4162 EVT VT, DebugLoc dl, SDValue Chain,
4163 SDValue Ptr, SDValue Offset,
4164 MachinePointerInfo PtrInfo, EVT MemVT,
4165 bool isVolatile, bool isNonTemporal, bool isInvariant,
4166 unsigned Alignment, const MDNode *TBAAInfo,
4167 const MDNode *Ranges) {
4168 assert(Chain.getValueType() == MVT::Other &&
4169 "Invalid chain type");
4170 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4171 Alignment = getEVTAlignment(VT);
4173 unsigned Flags = MachineMemOperand::MOLoad;
4175 Flags |= MachineMemOperand::MOVolatile;
4177 Flags |= MachineMemOperand::MONonTemporal;
4179 Flags |= MachineMemOperand::MOInvariant;
4181 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4184 PtrInfo = InferPointerInfo(Ptr, Offset);
4186 MachineFunction &MF = getMachineFunction();
4187 MachineMemOperand *MMO =
4188 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4190 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4194 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4195 EVT VT, DebugLoc dl, SDValue Chain,
4196 SDValue Ptr, SDValue Offset, EVT MemVT,
4197 MachineMemOperand *MMO) {
4199 ExtType = ISD::NON_EXTLOAD;
4200 } else if (ExtType == ISD::NON_EXTLOAD) {
4201 assert(VT == MemVT && "Non-extending load from different memory type!");
4204 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4205 "Should only be an extending load, not truncating!");
4206 assert(VT.isInteger() == MemVT.isInteger() &&
4207 "Cannot convert from FP to Int or Int -> FP!");
4208 assert(VT.isVector() == MemVT.isVector() &&
4209 "Cannot use trunc store to convert to or from a vector!");
4210 assert((!VT.isVector() ||
4211 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4212 "Cannot use trunc store to change the number of vector elements!");
4215 bool Indexed = AM != ISD::UNINDEXED;
4216 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4217 "Unindexed load with an offset!");
4219 SDVTList VTs = Indexed ?
4220 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4221 SDValue Ops[] = { Chain, Ptr, Offset };
4222 FoldingSetNodeID ID;
4223 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4224 ID.AddInteger(MemVT.getRawBits());
4225 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4226 MMO->isNonTemporal(),
4227 MMO->isInvariant()));
4229 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4230 cast<LoadSDNode>(E)->refineAlignment(MMO);
4231 return SDValue(E, 0);
4233 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4235 CSEMap.InsertNode(N, IP);
4236 AllNodes.push_back(N);
4237 return SDValue(N, 0);
4240 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4241 SDValue Chain, SDValue Ptr,
4242 MachinePointerInfo PtrInfo,
4243 bool isVolatile, bool isNonTemporal,
4244 bool isInvariant, unsigned Alignment,
4245 const MDNode *TBAAInfo,
4246 const MDNode *Ranges) {
4247 SDValue Undef = getUNDEF(Ptr.getValueType());
4248 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4249 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4253 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4254 SDValue Chain, SDValue Ptr,
4255 MachinePointerInfo PtrInfo, EVT MemVT,
4256 bool isVolatile, bool isNonTemporal,
4257 unsigned Alignment, const MDNode *TBAAInfo) {
4258 SDValue Undef = getUNDEF(Ptr.getValueType());
4259 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4260 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4266 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4267 SDValue Offset, ISD::MemIndexedMode AM) {
4268 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4269 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4270 "Load is already a indexed load!");
4271 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4272 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4273 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4274 false, LD->getAlignment());
4277 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4278 SDValue Ptr, MachinePointerInfo PtrInfo,
4279 bool isVolatile, bool isNonTemporal,
4280 unsigned Alignment, const MDNode *TBAAInfo) {
4281 assert(Chain.getValueType() == MVT::Other &&
4282 "Invalid chain type");
4283 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4284 Alignment = getEVTAlignment(Val.getValueType());
4286 unsigned Flags = MachineMemOperand::MOStore;
4288 Flags |= MachineMemOperand::MOVolatile;
4290 Flags |= MachineMemOperand::MONonTemporal;
4293 PtrInfo = InferPointerInfo(Ptr);
4295 MachineFunction &MF = getMachineFunction();
4296 MachineMemOperand *MMO =
4297 MF.getMachineMemOperand(PtrInfo, Flags,
4298 Val.getValueType().getStoreSize(), Alignment,
4301 return getStore(Chain, dl, Val, Ptr, MMO);
4304 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4305 SDValue Ptr, MachineMemOperand *MMO) {
4306 assert(Chain.getValueType() == MVT::Other &&
4307 "Invalid chain type");
4308 EVT VT = Val.getValueType();
4309 SDVTList VTs = getVTList(MVT::Other);
4310 SDValue Undef = getUNDEF(Ptr.getValueType());
4311 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4312 FoldingSetNodeID ID;
4313 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4314 ID.AddInteger(VT.getRawBits());
4315 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4316 MMO->isNonTemporal(), MMO->isInvariant()));
4318 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4319 cast<StoreSDNode>(E)->refineAlignment(MMO);
4320 return SDValue(E, 0);
4322 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4324 CSEMap.InsertNode(N, IP);
4325 AllNodes.push_back(N);
4326 return SDValue(N, 0);
4329 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4330 SDValue Ptr, MachinePointerInfo PtrInfo,
4331 EVT SVT,bool isVolatile, bool isNonTemporal,
4333 const MDNode *TBAAInfo) {
4334 assert(Chain.getValueType() == MVT::Other &&
4335 "Invalid chain type");
4336 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4337 Alignment = getEVTAlignment(SVT);
4339 unsigned Flags = MachineMemOperand::MOStore;
4341 Flags |= MachineMemOperand::MOVolatile;
4343 Flags |= MachineMemOperand::MONonTemporal;
4346 PtrInfo = InferPointerInfo(Ptr);
4348 MachineFunction &MF = getMachineFunction();
4349 MachineMemOperand *MMO =
4350 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4353 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4356 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4357 SDValue Ptr, EVT SVT,
4358 MachineMemOperand *MMO) {
4359 EVT VT = Val.getValueType();
4361 assert(Chain.getValueType() == MVT::Other &&
4362 "Invalid chain type");
4364 return getStore(Chain, dl, Val, Ptr, MMO);
4366 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4367 "Should only be a truncating store, not extending!");
4368 assert(VT.isInteger() == SVT.isInteger() &&
4369 "Can't do FP-INT conversion!");
4370 assert(VT.isVector() == SVT.isVector() &&
4371 "Cannot use trunc store to convert to or from a vector!");
4372 assert((!VT.isVector() ||
4373 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4374 "Cannot use trunc store to change the number of vector elements!");
4376 SDVTList VTs = getVTList(MVT::Other);
4377 SDValue Undef = getUNDEF(Ptr.getValueType());
4378 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4379 FoldingSetNodeID ID;
4380 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4381 ID.AddInteger(SVT.getRawBits());
4382 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4383 MMO->isNonTemporal(), MMO->isInvariant()));
4385 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4386 cast<StoreSDNode>(E)->refineAlignment(MMO);
4387 return SDValue(E, 0);
4389 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4391 CSEMap.InsertNode(N, IP);
4392 AllNodes.push_back(N);
4393 return SDValue(N, 0);
4397 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4398 SDValue Offset, ISD::MemIndexedMode AM) {
4399 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4400 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4401 "Store is already a indexed store!");
4402 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4403 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4404 FoldingSetNodeID ID;
4405 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4406 ID.AddInteger(ST->getMemoryVT().getRawBits());
4407 ID.AddInteger(ST->getRawSubclassData());
4409 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4410 return SDValue(E, 0);
4412 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4413 ST->isTruncatingStore(),
4415 ST->getMemOperand());
4416 CSEMap.InsertNode(N, IP);
4417 AllNodes.push_back(N);
4418 return SDValue(N, 0);
4421 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4422 SDValue Chain, SDValue Ptr,
4425 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4426 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4429 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4430 const SDUse *Ops, unsigned NumOps) {
4432 case 0: return getNode(Opcode, DL, VT);
4433 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4434 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4435 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4439 // Copy from an SDUse array into an SDValue array for use with
4440 // the regular getNode logic.
4441 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4442 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4445 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4446 const SDValue *Ops, unsigned NumOps) {
4448 case 0: return getNode(Opcode, DL, VT);
4449 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4450 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4451 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4457 case ISD::SELECT_CC: {
4458 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4459 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4460 "LHS and RHS of condition must have same type!");
4461 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4462 "True and False arms of SelectCC must have same type!");
4463 assert(Ops[2].getValueType() == VT &&
4464 "select_cc node must be of same type as true and false value!");
4468 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4469 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4470 "LHS/RHS of comparison should match types!");
4477 SDVTList VTs = getVTList(VT);
4479 if (VT != MVT::Glue) {
4480 FoldingSetNodeID ID;
4481 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4484 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4485 return SDValue(E, 0);
4487 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4488 CSEMap.InsertNode(N, IP);
4490 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4493 AllNodes.push_back(N);
4497 return SDValue(N, 0);
4500 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4501 const std::vector<EVT> &ResultTys,
4502 const SDValue *Ops, unsigned NumOps) {
4503 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4507 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4508 const EVT *VTs, unsigned NumVTs,
4509 const SDValue *Ops, unsigned NumOps) {
4511 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4512 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4515 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4516 const SDValue *Ops, unsigned NumOps) {
4517 if (VTList.NumVTs == 1)
4518 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4522 // FIXME: figure out how to safely handle things like
4523 // int foo(int x) { return 1 << (x & 255); }
4524 // int bar() { return foo(256); }
4525 case ISD::SRA_PARTS:
4526 case ISD::SRL_PARTS:
4527 case ISD::SHL_PARTS:
4528 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4529 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4530 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4531 else if (N3.getOpcode() == ISD::AND)
4532 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4533 // If the and is only masking out bits that cannot effect the shift,
4534 // eliminate the and.
4535 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4536 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4537 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4543 // Memoize the node unless it returns a flag.
4545 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4546 FoldingSetNodeID ID;
4547 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4549 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4550 return SDValue(E, 0);
4553 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4554 } else if (NumOps == 2) {
4555 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4556 } else if (NumOps == 3) {
4557 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4560 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4562 CSEMap.InsertNode(N, IP);
4565 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4566 } else if (NumOps == 2) {
4567 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4568 } else if (NumOps == 3) {
4569 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4572 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4575 AllNodes.push_back(N);
4579 return SDValue(N, 0);
4582 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4583 return getNode(Opcode, DL, VTList, 0, 0);
4586 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4588 SDValue Ops[] = { N1 };
4589 return getNode(Opcode, DL, VTList, Ops, 1);
4592 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4593 SDValue N1, SDValue N2) {
4594 SDValue Ops[] = { N1, N2 };
4595 return getNode(Opcode, DL, VTList, Ops, 2);
4598 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4599 SDValue N1, SDValue N2, SDValue N3) {
4600 SDValue Ops[] = { N1, N2, N3 };
4601 return getNode(Opcode, DL, VTList, Ops, 3);
4604 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4605 SDValue N1, SDValue N2, SDValue N3,
4607 SDValue Ops[] = { N1, N2, N3, N4 };
4608 return getNode(Opcode, DL, VTList, Ops, 4);
4611 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4612 SDValue N1, SDValue N2, SDValue N3,
4613 SDValue N4, SDValue N5) {
4614 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4615 return getNode(Opcode, DL, VTList, Ops, 5);
4618 SDVTList SelectionDAG::getVTList(EVT VT) {
4619 return makeVTList(SDNode::getValueTypeList(VT), 1);
4622 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4623 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4624 E = VTList.rend(); I != E; ++I)
4625 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4628 EVT *Array = Allocator.Allocate<EVT>(2);
4631 SDVTList Result = makeVTList(Array, 2);
4632 VTList.push_back(Result);
4636 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4637 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4638 E = VTList.rend(); I != E; ++I)
4639 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4643 EVT *Array = Allocator.Allocate<EVT>(3);
4647 SDVTList Result = makeVTList(Array, 3);
4648 VTList.push_back(Result);
4652 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4653 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4654 E = VTList.rend(); I != E; ++I)
4655 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4656 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4659 EVT *Array = Allocator.Allocate<EVT>(4);
4664 SDVTList Result = makeVTList(Array, 4);
4665 VTList.push_back(Result);
4669 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4671 case 0: llvm_unreachable("Cannot have nodes without results!");
4672 case 1: return getVTList(VTs[0]);
4673 case 2: return getVTList(VTs[0], VTs[1]);
4674 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4675 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4679 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4680 E = VTList.rend(); I != E; ++I) {
4681 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4684 if (std::equal(&VTs[2], &VTs[NumVTs], &I->VTs[2]))
4688 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4689 std::copy(VTs, VTs+NumVTs, Array);
4690 SDVTList Result = makeVTList(Array, NumVTs);
4691 VTList.push_back(Result);
4696 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4697 /// specified operands. If the resultant node already exists in the DAG,
4698 /// this does not modify the specified node, instead it returns the node that
4699 /// already exists. If the resultant node does not exist in the DAG, the
4700 /// input node is returned. As a degenerate case, if you specify the same
4701 /// input operands as the node already has, the input node is returned.
4702 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4703 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4705 // Check to see if there is no change.
4706 if (Op == N->getOperand(0)) return N;
4708 // See if the modified node already exists.
4709 void *InsertPos = 0;
4710 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4713 // Nope it doesn't. Remove the node from its current place in the maps.
4715 if (!RemoveNodeFromCSEMaps(N))
4718 // Now we update the operands.
4719 N->OperandList[0].set(Op);
4721 // If this gets put into a CSE map, add it.
4722 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4726 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4727 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4729 // Check to see if there is no change.
4730 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4731 return N; // No operands changed, just return the input node.
4733 // See if the modified node already exists.
4734 void *InsertPos = 0;
4735 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4738 // Nope it doesn't. Remove the node from its current place in the maps.
4740 if (!RemoveNodeFromCSEMaps(N))
4743 // Now we update the operands.
4744 if (N->OperandList[0] != Op1)
4745 N->OperandList[0].set(Op1);
4746 if (N->OperandList[1] != Op2)
4747 N->OperandList[1].set(Op2);
4749 // If this gets put into a CSE map, add it.
4750 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4754 SDNode *SelectionDAG::
4755 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4756 SDValue Ops[] = { Op1, Op2, Op3 };
4757 return UpdateNodeOperands(N, Ops, 3);
4760 SDNode *SelectionDAG::
4761 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4762 SDValue Op3, SDValue Op4) {
4763 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4764 return UpdateNodeOperands(N, Ops, 4);
4767 SDNode *SelectionDAG::
4768 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4769 SDValue Op3, SDValue Op4, SDValue Op5) {
4770 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4771 return UpdateNodeOperands(N, Ops, 5);
4774 SDNode *SelectionDAG::
4775 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4776 assert(N->getNumOperands() == NumOps &&
4777 "Update with wrong number of operands");
4779 // Check to see if there is no change.
4780 bool AnyChange = false;
4781 for (unsigned i = 0; i != NumOps; ++i) {
4782 if (Ops[i] != N->getOperand(i)) {
4788 // No operands changed, just return the input node.
4789 if (!AnyChange) return N;
4791 // See if the modified node already exists.
4792 void *InsertPos = 0;
4793 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4796 // Nope it doesn't. Remove the node from its current place in the maps.
4798 if (!RemoveNodeFromCSEMaps(N))
4801 // Now we update the operands.
4802 for (unsigned i = 0; i != NumOps; ++i)
4803 if (N->OperandList[i] != Ops[i])
4804 N->OperandList[i].set(Ops[i]);
4806 // If this gets put into a CSE map, add it.
4807 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4811 /// DropOperands - Release the operands and set this node to have
4813 void SDNode::DropOperands() {
4814 // Unlike the code in MorphNodeTo that does this, we don't need to
4815 // watch for dead nodes here.
4816 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4822 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4825 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4827 SDVTList VTs = getVTList(VT);
4828 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4831 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4832 EVT VT, SDValue Op1) {
4833 SDVTList VTs = getVTList(VT);
4834 SDValue Ops[] = { Op1 };
4835 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4838 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4839 EVT VT, SDValue Op1,
4841 SDVTList VTs = getVTList(VT);
4842 SDValue Ops[] = { Op1, Op2 };
4843 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4846 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4847 EVT VT, SDValue Op1,
4848 SDValue Op2, SDValue Op3) {
4849 SDVTList VTs = getVTList(VT);
4850 SDValue Ops[] = { Op1, Op2, Op3 };
4851 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4854 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4855 EVT VT, const SDValue *Ops,
4857 SDVTList VTs = getVTList(VT);
4858 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4861 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4862 EVT VT1, EVT VT2, const SDValue *Ops,
4864 SDVTList VTs = getVTList(VT1, VT2);
4865 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4868 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4870 SDVTList VTs = getVTList(VT1, VT2);
4871 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4874 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4875 EVT VT1, EVT VT2, EVT VT3,
4876 const SDValue *Ops, unsigned NumOps) {
4877 SDVTList VTs = getVTList(VT1, VT2, VT3);
4878 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4881 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4882 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4883 const SDValue *Ops, unsigned NumOps) {
4884 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4885 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4888 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4891 SDVTList VTs = getVTList(VT1, VT2);
4892 SDValue Ops[] = { Op1 };
4893 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4896 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4898 SDValue Op1, SDValue Op2) {
4899 SDVTList VTs = getVTList(VT1, VT2);
4900 SDValue Ops[] = { Op1, Op2 };
4901 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4904 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4906 SDValue Op1, SDValue Op2,
4908 SDVTList VTs = getVTList(VT1, VT2);
4909 SDValue Ops[] = { Op1, Op2, Op3 };
4910 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4913 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4914 EVT VT1, EVT VT2, EVT VT3,
4915 SDValue Op1, SDValue Op2,
4917 SDVTList VTs = getVTList(VT1, VT2, VT3);
4918 SDValue Ops[] = { Op1, Op2, Op3 };
4919 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4922 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4923 SDVTList VTs, const SDValue *Ops,
4925 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
4926 // Reset the NodeID to -1.
4931 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
4932 /// the line number information on the merged node since it is not possible to
4933 /// preserve the information that operation is associated with multiple lines.
4934 /// This will make the debugger working better at -O0, were there is a higher
4935 /// probability having other instructions associated with that line.
4937 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
4938 DebugLoc NLoc = N->getDebugLoc();
4939 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
4940 N->setDebugLoc(DebugLoc());
4945 /// MorphNodeTo - This *mutates* the specified node to have the specified
4946 /// return type, opcode, and operands.
4948 /// Note that MorphNodeTo returns the resultant node. If there is already a
4949 /// node of the specified opcode and operands, it returns that node instead of
4950 /// the current one. Note that the DebugLoc need not be the same.
4952 /// Using MorphNodeTo is faster than creating a new node and swapping it in
4953 /// with ReplaceAllUsesWith both because it often avoids allocating a new
4954 /// node, and because it doesn't require CSE recalculation for any of
4955 /// the node's users.
4957 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
4958 SDVTList VTs, const SDValue *Ops,
4960 // If an identical node already exists, use it.
4962 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
4963 FoldingSetNodeID ID;
4964 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
4965 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
4966 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
4969 if (!RemoveNodeFromCSEMaps(N))
4972 // Start the morphing.
4974 N->ValueList = VTs.VTs;
4975 N->NumValues = VTs.NumVTs;
4977 // Clear the operands list, updating used nodes to remove this from their
4978 // use list. Keep track of any operands that become dead as a result.
4979 SmallPtrSet<SDNode*, 16> DeadNodeSet;
4980 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
4982 SDNode *Used = Use.getNode();
4984 if (Used->use_empty())
4985 DeadNodeSet.insert(Used);
4988 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
4989 // Initialize the memory references information.
4990 MN->setMemRefs(0, 0);
4991 // If NumOps is larger than the # of operands we can have in a
4992 // MachineSDNode, reallocate the operand list.
4993 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
4994 if (MN->OperandsNeedDelete)
4995 delete[] MN->OperandList;
4996 if (NumOps > array_lengthof(MN->LocalOperands))
4997 // We're creating a final node that will live unmorphed for the
4998 // remainder of the current SelectionDAG iteration, so we can allocate
4999 // the operands directly out of a pool with no recycling metadata.
5000 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5003 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5004 MN->OperandsNeedDelete = false;
5006 MN->InitOperands(MN->OperandList, Ops, NumOps);
5008 // If NumOps is larger than the # of operands we currently have, reallocate
5009 // the operand list.
5010 if (NumOps > N->NumOperands) {
5011 if (N->OperandsNeedDelete)
5012 delete[] N->OperandList;
5013 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5014 N->OperandsNeedDelete = true;
5016 N->InitOperands(N->OperandList, Ops, NumOps);
5019 // Delete any nodes that are still dead after adding the uses for the
5021 if (!DeadNodeSet.empty()) {
5022 SmallVector<SDNode *, 16> DeadNodes;
5023 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5024 E = DeadNodeSet.end(); I != E; ++I)
5025 if ((*I)->use_empty())
5026 DeadNodes.push_back(*I);
5027 RemoveDeadNodes(DeadNodes);
5031 CSEMap.InsertNode(N, IP); // Memoize the new node.
5036 /// getMachineNode - These are used for target selectors to create a new node
5037 /// with specified return type(s), MachineInstr opcode, and operands.
5039 /// Note that getMachineNode returns the resultant node. If there is already a
5040 /// node of the specified opcode and operands, it returns that node instead of
5041 /// the current one.
5043 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5044 SDVTList VTs = getVTList(VT);
5045 return getMachineNode(Opcode, dl, VTs, 0, 0);
5049 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5050 SDVTList VTs = getVTList(VT);
5051 SDValue Ops[] = { Op1 };
5052 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5056 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5057 SDValue Op1, SDValue Op2) {
5058 SDVTList VTs = getVTList(VT);
5059 SDValue Ops[] = { Op1, Op2 };
5060 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5064 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5065 SDValue Op1, SDValue Op2, SDValue Op3) {
5066 SDVTList VTs = getVTList(VT);
5067 SDValue Ops[] = { Op1, Op2, Op3 };
5068 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5072 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5073 const SDValue *Ops, unsigned NumOps) {
5074 SDVTList VTs = getVTList(VT);
5075 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5079 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5080 SDVTList VTs = getVTList(VT1, VT2);
5081 return getMachineNode(Opcode, dl, VTs, 0, 0);
5085 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5086 EVT VT1, EVT VT2, SDValue Op1) {
5087 SDVTList VTs = getVTList(VT1, VT2);
5088 SDValue Ops[] = { Op1 };
5089 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5093 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5094 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5095 SDVTList VTs = getVTList(VT1, VT2);
5096 SDValue Ops[] = { Op1, Op2 };
5097 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5101 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5102 EVT VT1, EVT VT2, SDValue Op1,
5103 SDValue Op2, SDValue Op3) {
5104 SDVTList VTs = getVTList(VT1, VT2);
5105 SDValue Ops[] = { Op1, Op2, Op3 };
5106 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5110 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5112 const SDValue *Ops, unsigned NumOps) {
5113 SDVTList VTs = getVTList(VT1, VT2);
5114 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5118 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5119 EVT VT1, EVT VT2, EVT VT3,
5120 SDValue Op1, SDValue Op2) {
5121 SDVTList VTs = getVTList(VT1, VT2, VT3);
5122 SDValue Ops[] = { Op1, Op2 };
5123 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5127 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5128 EVT VT1, EVT VT2, EVT VT3,
5129 SDValue Op1, SDValue Op2, SDValue Op3) {
5130 SDVTList VTs = getVTList(VT1, VT2, VT3);
5131 SDValue Ops[] = { Op1, Op2, Op3 };
5132 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5136 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5137 EVT VT1, EVT VT2, EVT VT3,
5138 const SDValue *Ops, unsigned NumOps) {
5139 SDVTList VTs = getVTList(VT1, VT2, VT3);
5140 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5144 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5145 EVT VT2, EVT VT3, EVT VT4,
5146 const SDValue *Ops, unsigned NumOps) {
5147 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5148 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5152 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5153 const std::vector<EVT> &ResultTys,
5154 const SDValue *Ops, unsigned NumOps) {
5155 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5156 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5160 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5161 const SDValue *Ops, unsigned NumOps) {
5162 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5167 FoldingSetNodeID ID;
5168 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5170 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5171 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5175 // Allocate a new MachineSDNode.
5176 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5178 // Initialize the operands list.
5179 if (NumOps > array_lengthof(N->LocalOperands))
5180 // We're creating a final node that will live unmorphed for the
5181 // remainder of the current SelectionDAG iteration, so we can allocate
5182 // the operands directly out of a pool with no recycling metadata.
5183 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5186 N->InitOperands(N->LocalOperands, Ops, NumOps);
5187 N->OperandsNeedDelete = false;
5190 CSEMap.InsertNode(N, IP);
5192 AllNodes.push_back(N);
5194 VerifyMachineNode(N);
5199 /// getTargetExtractSubreg - A convenience function for creating
5200 /// TargetOpcode::EXTRACT_SUBREG nodes.
5202 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5204 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5205 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5206 VT, Operand, SRIdxVal);
5207 return SDValue(Subreg, 0);
5210 /// getTargetInsertSubreg - A convenience function for creating
5211 /// TargetOpcode::INSERT_SUBREG nodes.
5213 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5214 SDValue Operand, SDValue Subreg) {
5215 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5216 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5217 VT, Operand, Subreg, SRIdxVal);
5218 return SDValue(Result, 0);
5221 /// getNodeIfExists - Get the specified node if it's already available, or
5222 /// else return NULL.
5223 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5224 const SDValue *Ops, unsigned NumOps) {
5225 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5226 FoldingSetNodeID ID;
5227 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5229 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5235 /// getDbgValue - Creates a SDDbgValue node.
5238 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5239 DebugLoc DL, unsigned O) {
5240 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5244 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5245 DebugLoc DL, unsigned O) {
5246 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5250 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5251 DebugLoc DL, unsigned O) {
5252 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5257 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5258 /// pointed to by a use iterator is deleted, increment the use iterator
5259 /// so that it doesn't dangle.
5261 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5262 SDNode::use_iterator &UI;
5263 SDNode::use_iterator &UE;
5265 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5266 // Increment the iterator as needed.
5267 while (UI != UE && N == *UI)
5272 RAUWUpdateListener(SelectionDAG &d,
5273 SDNode::use_iterator &ui,
5274 SDNode::use_iterator &ue)
5275 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5280 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5281 /// This can cause recursive merging of nodes in the DAG.
5283 /// This version assumes From has a single result value.
5285 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5286 SDNode *From = FromN.getNode();
5287 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5288 "Cannot replace with this method!");
5289 assert(From != To.getNode() && "Cannot replace uses of with self");
5291 // Iterate over all the existing uses of From. New uses will be added
5292 // to the beginning of the use list, which we avoid visiting.
5293 // This specifically avoids visiting uses of From that arise while the
5294 // replacement is happening, because any such uses would be the result
5295 // of CSE: If an existing node looks like From after one of its operands
5296 // is replaced by To, we don't want to replace of all its users with To
5297 // too. See PR3018 for more info.
5298 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5299 RAUWUpdateListener Listener(*this, UI, UE);
5303 // This node is about to morph, remove its old self from the CSE maps.
5304 RemoveNodeFromCSEMaps(User);
5306 // A user can appear in a use list multiple times, and when this
5307 // happens the uses are usually next to each other in the list.
5308 // To help reduce the number of CSE recomputations, process all
5309 // the uses of this user that we can find this way.
5311 SDUse &Use = UI.getUse();
5314 } while (UI != UE && *UI == User);
5316 // Now that we have modified User, add it back to the CSE maps. If it
5317 // already exists there, recursively merge the results together.
5318 AddModifiedNodeToCSEMaps(User);
5321 // If we just RAUW'd the root, take note.
5322 if (FromN == getRoot())
5326 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5327 /// This can cause recursive merging of nodes in the DAG.
5329 /// This version assumes that for each value of From, there is a
5330 /// corresponding value in To in the same position with the same type.
5332 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5334 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5335 assert((!From->hasAnyUseOfValue(i) ||
5336 From->getValueType(i) == To->getValueType(i)) &&
5337 "Cannot use this version of ReplaceAllUsesWith!");
5340 // Handle the trivial case.
5344 // Iterate over just the existing users of From. See the comments in
5345 // the ReplaceAllUsesWith above.
5346 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5347 RAUWUpdateListener Listener(*this, UI, UE);
5351 // This node is about to morph, remove its old self from the CSE maps.
5352 RemoveNodeFromCSEMaps(User);
5354 // A user can appear in a use list multiple times, and when this
5355 // happens the uses are usually next to each other in the list.
5356 // To help reduce the number of CSE recomputations, process all
5357 // the uses of this user that we can find this way.
5359 SDUse &Use = UI.getUse();
5362 } while (UI != UE && *UI == User);
5364 // Now that we have modified User, add it back to the CSE maps. If it
5365 // already exists there, recursively merge the results together.
5366 AddModifiedNodeToCSEMaps(User);
5369 // If we just RAUW'd the root, take note.
5370 if (From == getRoot().getNode())
5371 setRoot(SDValue(To, getRoot().getResNo()));
5374 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5375 /// This can cause recursive merging of nodes in the DAG.
5377 /// This version can replace From with any result values. To must match the
5378 /// number and types of values returned by From.
5379 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5380 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5381 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5383 // Iterate over just the existing users of From. See the comments in
5384 // the ReplaceAllUsesWith above.
5385 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5386 RAUWUpdateListener Listener(*this, UI, UE);
5390 // This node is about to morph, remove its old self from the CSE maps.
5391 RemoveNodeFromCSEMaps(User);
5393 // A user can appear in a use list multiple times, and when this
5394 // happens the uses are usually next to each other in the list.
5395 // To help reduce the number of CSE recomputations, process all
5396 // the uses of this user that we can find this way.
5398 SDUse &Use = UI.getUse();
5399 const SDValue &ToOp = To[Use.getResNo()];
5402 } while (UI != UE && *UI == User);
5404 // Now that we have modified User, add it back to the CSE maps. If it
5405 // already exists there, recursively merge the results together.
5406 AddModifiedNodeToCSEMaps(User);
5409 // If we just RAUW'd the root, take note.
5410 if (From == getRoot().getNode())
5411 setRoot(SDValue(To[getRoot().getResNo()]));
5414 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5415 /// uses of other values produced by From.getNode() alone. The Deleted
5416 /// vector is handled the same way as for ReplaceAllUsesWith.
5417 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5418 // Handle the really simple, really trivial case efficiently.
5419 if (From == To) return;
5421 // Handle the simple, trivial, case efficiently.
5422 if (From.getNode()->getNumValues() == 1) {
5423 ReplaceAllUsesWith(From, To);
5427 // Iterate over just the existing users of From. See the comments in
5428 // the ReplaceAllUsesWith above.
5429 SDNode::use_iterator UI = From.getNode()->use_begin(),
5430 UE = From.getNode()->use_end();
5431 RAUWUpdateListener Listener(*this, UI, UE);
5434 bool UserRemovedFromCSEMaps = false;
5436 // A user can appear in a use list multiple times, and when this
5437 // happens the uses are usually next to each other in the list.
5438 // To help reduce the number of CSE recomputations, process all
5439 // the uses of this user that we can find this way.
5441 SDUse &Use = UI.getUse();
5443 // Skip uses of different values from the same node.
5444 if (Use.getResNo() != From.getResNo()) {
5449 // If this node hasn't been modified yet, it's still in the CSE maps,
5450 // so remove its old self from the CSE maps.
5451 if (!UserRemovedFromCSEMaps) {
5452 RemoveNodeFromCSEMaps(User);
5453 UserRemovedFromCSEMaps = true;
5458 } while (UI != UE && *UI == User);
5460 // We are iterating over all uses of the From node, so if a use
5461 // doesn't use the specific value, no changes are made.
5462 if (!UserRemovedFromCSEMaps)
5465 // Now that we have modified User, add it back to the CSE maps. If it
5466 // already exists there, recursively merge the results together.
5467 AddModifiedNodeToCSEMaps(User);
5470 // If we just RAUW'd the root, take note.
5471 if (From == getRoot())
5476 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5477 /// to record information about a use.
5484 /// operator< - Sort Memos by User.
5485 bool operator<(const UseMemo &L, const UseMemo &R) {
5486 return (intptr_t)L.User < (intptr_t)R.User;
5490 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5491 /// uses of other values produced by From.getNode() alone. The same value
5492 /// may appear in both the From and To list. The Deleted vector is
5493 /// handled the same way as for ReplaceAllUsesWith.
5494 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5497 // Handle the simple, trivial case efficiently.
5499 return ReplaceAllUsesOfValueWith(*From, *To);
5501 // Read up all the uses and make records of them. This helps
5502 // processing new uses that are introduced during the
5503 // replacement process.
5504 SmallVector<UseMemo, 4> Uses;
5505 for (unsigned i = 0; i != Num; ++i) {
5506 unsigned FromResNo = From[i].getResNo();
5507 SDNode *FromNode = From[i].getNode();
5508 for (SDNode::use_iterator UI = FromNode->use_begin(),
5509 E = FromNode->use_end(); UI != E; ++UI) {
5510 SDUse &Use = UI.getUse();
5511 if (Use.getResNo() == FromResNo) {
5512 UseMemo Memo = { *UI, i, &Use };
5513 Uses.push_back(Memo);
5518 // Sort the uses, so that all the uses from a given User are together.
5519 std::sort(Uses.begin(), Uses.end());
5521 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5522 UseIndex != UseIndexEnd; ) {
5523 // We know that this user uses some value of From. If it is the right
5524 // value, update it.
5525 SDNode *User = Uses[UseIndex].User;
5527 // This node is about to morph, remove its old self from the CSE maps.
5528 RemoveNodeFromCSEMaps(User);
5530 // The Uses array is sorted, so all the uses for a given User
5531 // are next to each other in the list.
5532 // To help reduce the number of CSE recomputations, process all
5533 // the uses of this user that we can find this way.
5535 unsigned i = Uses[UseIndex].Index;
5536 SDUse &Use = *Uses[UseIndex].Use;
5540 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5542 // Now that we have modified User, add it back to the CSE maps. If it
5543 // already exists there, recursively merge the results together.
5544 AddModifiedNodeToCSEMaps(User);
5548 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5549 /// based on their topological order. It returns the maximum id and a vector
5550 /// of the SDNodes* in assigned order by reference.
5551 unsigned SelectionDAG::AssignTopologicalOrder() {
5553 unsigned DAGSize = 0;
5555 // SortedPos tracks the progress of the algorithm. Nodes before it are
5556 // sorted, nodes after it are unsorted. When the algorithm completes
5557 // it is at the end of the list.
5558 allnodes_iterator SortedPos = allnodes_begin();
5560 // Visit all the nodes. Move nodes with no operands to the front of
5561 // the list immediately. Annotate nodes that do have operands with their
5562 // operand count. Before we do this, the Node Id fields of the nodes
5563 // may contain arbitrary values. After, the Node Id fields for nodes
5564 // before SortedPos will contain the topological sort index, and the
5565 // Node Id fields for nodes At SortedPos and after will contain the
5566 // count of outstanding operands.
5567 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5570 unsigned Degree = N->getNumOperands();
5572 // A node with no uses, add it to the result array immediately.
5573 N->setNodeId(DAGSize++);
5574 allnodes_iterator Q = N;
5576 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5577 assert(SortedPos != AllNodes.end() && "Overran node list");
5580 // Temporarily use the Node Id as scratch space for the degree count.
5581 N->setNodeId(Degree);
5585 // Visit all the nodes. As we iterate, move nodes into sorted order,
5586 // such that by the time the end is reached all nodes will be sorted.
5587 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5590 // N is in sorted position, so all its uses have one less operand
5591 // that needs to be sorted.
5592 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5595 unsigned Degree = P->getNodeId();
5596 assert(Degree != 0 && "Invalid node degree");
5599 // All of P's operands are sorted, so P may sorted now.
5600 P->setNodeId(DAGSize++);
5602 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5603 assert(SortedPos != AllNodes.end() && "Overran node list");
5606 // Update P's outstanding operand count.
5607 P->setNodeId(Degree);
5610 if (I == SortedPos) {
5613 dbgs() << "Overran sorted position:\n";
5616 llvm_unreachable(0);
5620 assert(SortedPos == AllNodes.end() &&
5621 "Topological sort incomplete!");
5622 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5623 "First node in topological sort is not the entry token!");
5624 assert(AllNodes.front().getNodeId() == 0 &&
5625 "First node in topological sort has non-zero id!");
5626 assert(AllNodes.front().getNumOperands() == 0 &&
5627 "First node in topological sort has operands!");
5628 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5629 "Last node in topologic sort has unexpected id!");
5630 assert(AllNodes.back().use_empty() &&
5631 "Last node in topologic sort has users!");
5632 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5636 /// AssignOrdering - Assign an order to the SDNode.
5637 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5638 assert(SD && "Trying to assign an order to a null node!");
5639 Ordering->add(SD, Order);
5642 /// GetOrdering - Get the order for the SDNode.
5643 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5644 assert(SD && "Trying to get the order of a null node!");
5645 return Ordering->getOrder(SD);
5648 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5649 /// value is produced by SD.
5650 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5651 DbgInfo->add(DB, SD, isParameter);
5653 SD->setHasDebugValue(true);
5656 /// TransferDbgValues - Transfer SDDbgValues.
5657 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5658 if (From == To || !From.getNode()->getHasDebugValue())
5660 SDNode *FromNode = From.getNode();
5661 SDNode *ToNode = To.getNode();
5662 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5663 SmallVector<SDDbgValue *, 2> ClonedDVs;
5664 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5666 SDDbgValue *Dbg = *I;
5667 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5668 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5669 Dbg->getOffset(), Dbg->getDebugLoc(),
5671 ClonedDVs.push_back(Clone);
5674 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5675 E = ClonedDVs.end(); I != E; ++I)
5676 AddDbgValue(*I, ToNode, false);
5679 //===----------------------------------------------------------------------===//
5681 //===----------------------------------------------------------------------===//
5683 HandleSDNode::~HandleSDNode() {
5687 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5688 const GlobalValue *GA,
5689 EVT VT, int64_t o, unsigned char TF)
5690 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5694 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5695 MachineMemOperand *mmo)
5696 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5697 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5698 MMO->isNonTemporal(), MMO->isInvariant());
5699 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5700 assert(isNonTemporal() == MMO->isNonTemporal() &&
5701 "Non-temporal encoding error!");
5702 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5705 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5706 const SDValue *Ops, unsigned NumOps, EVT memvt,
5707 MachineMemOperand *mmo)
5708 : SDNode(Opc, dl, VTs, Ops, NumOps),
5709 MemoryVT(memvt), MMO(mmo) {
5710 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5711 MMO->isNonTemporal(), MMO->isInvariant());
5712 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5713 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5716 /// Profile - Gather unique data for the node.
5718 void SDNode::Profile(FoldingSetNodeID &ID) const {
5719 AddNodeIDNode(ID, this);
5724 std::vector<EVT> VTs;
5727 VTs.reserve(MVT::LAST_VALUETYPE);
5728 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5729 VTs.push_back(MVT((MVT::SimpleValueType)i));
5734 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5735 static ManagedStatic<EVTArray> SimpleVTArray;
5736 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5738 /// getValueTypeList - Return a pointer to the specified value type.
5740 const EVT *SDNode::getValueTypeList(EVT VT) {
5741 if (VT.isExtended()) {
5742 sys::SmartScopedLock<true> Lock(*VTMutex);
5743 return &(*EVTs->insert(VT).first);
5745 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5746 "Value type out of range!");
5747 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5751 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5752 /// indicated value. This method ignores uses of other values defined by this
5754 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5755 assert(Value < getNumValues() && "Bad value!");
5757 // TODO: Only iterate over uses of a given value of the node
5758 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5759 if (UI.getUse().getResNo() == Value) {
5766 // Found exactly the right number of uses?
5771 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5772 /// value. This method ignores uses of other values defined by this operation.
5773 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5774 assert(Value < getNumValues() && "Bad value!");
5776 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5777 if (UI.getUse().getResNo() == Value)
5784 /// isOnlyUserOf - Return true if this node is the only use of N.
5786 bool SDNode::isOnlyUserOf(SDNode *N) const {
5788 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5799 /// isOperand - Return true if this node is an operand of N.
5801 bool SDValue::isOperandOf(SDNode *N) const {
5802 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5803 if (*this == N->getOperand(i))
5808 bool SDNode::isOperandOf(SDNode *N) const {
5809 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5810 if (this == N->OperandList[i].getNode())
5815 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5816 /// be a chain) reaches the specified operand without crossing any
5817 /// side-effecting instructions on any chain path. In practice, this looks
5818 /// through token factors and non-volatile loads. In order to remain efficient,
5819 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5820 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5821 unsigned Depth) const {
5822 if (*this == Dest) return true;
5824 // Don't search too deeply, we just want to be able to see through
5825 // TokenFactor's etc.
5826 if (Depth == 0) return false;
5828 // If this is a token factor, all inputs to the TF happen in parallel. If any
5829 // of the operands of the TF does not reach dest, then we cannot do the xform.
5830 if (getOpcode() == ISD::TokenFactor) {
5831 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5832 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5837 // Loads don't have side effects, look through them.
5838 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5839 if (!Ld->isVolatile())
5840 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5845 /// hasPredecessor - Return true if N is a predecessor of this node.
5846 /// N is either an operand of this node, or can be reached by recursively
5847 /// traversing up the operands.
5848 /// NOTE: This is an expensive method. Use it carefully.
5849 bool SDNode::hasPredecessor(const SDNode *N) const {
5850 SmallPtrSet<const SDNode *, 32> Visited;
5851 SmallVector<const SDNode *, 16> Worklist;
5852 return hasPredecessorHelper(N, Visited, Worklist);
5855 bool SDNode::hasPredecessorHelper(const SDNode *N,
5856 SmallPtrSet<const SDNode *, 32> &Visited,
5857 SmallVector<const SDNode *, 16> &Worklist) const {
5858 if (Visited.empty()) {
5859 Worklist.push_back(this);
5861 // Take a look in the visited set. If we've already encountered this node
5862 // we needn't search further.
5863 if (Visited.count(N))
5867 // Haven't visited N yet. Continue the search.
5868 while (!Worklist.empty()) {
5869 const SDNode *M = Worklist.pop_back_val();
5870 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5871 SDNode *Op = M->getOperand(i).getNode();
5872 if (Visited.insert(Op))
5873 Worklist.push_back(Op);
5882 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5883 assert(Num < NumOperands && "Invalid child # of SDNode!");
5884 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5887 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
5888 assert(N->getNumValues() == 1 &&
5889 "Can't unroll a vector with multiple results!");
5891 EVT VT = N->getValueType(0);
5892 unsigned NE = VT.getVectorNumElements();
5893 EVT EltVT = VT.getVectorElementType();
5894 DebugLoc dl = N->getDebugLoc();
5896 SmallVector<SDValue, 8> Scalars;
5897 SmallVector<SDValue, 4> Operands(N->getNumOperands());
5899 // If ResNE is 0, fully unroll the vector op.
5902 else if (NE > ResNE)
5906 for (i= 0; i != NE; ++i) {
5907 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
5908 SDValue Operand = N->getOperand(j);
5909 EVT OperandVT = Operand.getValueType();
5910 if (OperandVT.isVector()) {
5911 // A vector operand; extract a single element.
5912 EVT OperandEltVT = OperandVT.getVectorElementType();
5913 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
5916 getConstant(i, TLI.getPointerTy()));
5918 // A scalar operand; just use it as is.
5919 Operands[j] = Operand;
5923 switch (N->getOpcode()) {
5925 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5926 &Operands[0], Operands.size()));
5929 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
5930 &Operands[0], Operands.size()));
5937 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
5938 getShiftAmountOperand(Operands[0].getValueType(),
5941 case ISD::SIGN_EXTEND_INREG:
5942 case ISD::FP_ROUND_INREG: {
5943 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
5944 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5946 getValueType(ExtVT)));
5951 for (; i < ResNE; ++i)
5952 Scalars.push_back(getUNDEF(EltVT));
5954 return getNode(ISD::BUILD_VECTOR, dl,
5955 EVT::getVectorVT(*getContext(), EltVT, ResNE),
5956 &Scalars[0], Scalars.size());
5960 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
5961 /// location that is 'Dist' units away from the location that the 'Base' load
5962 /// is loading from.
5963 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
5964 unsigned Bytes, int Dist) const {
5965 if (LD->getChain() != Base->getChain())
5967 EVT VT = LD->getValueType(0);
5968 if (VT.getSizeInBits() / 8 != Bytes)
5971 SDValue Loc = LD->getOperand(1);
5972 SDValue BaseLoc = Base->getOperand(1);
5973 if (Loc.getOpcode() == ISD::FrameIndex) {
5974 if (BaseLoc.getOpcode() != ISD::FrameIndex)
5976 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
5977 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
5978 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
5979 int FS = MFI->getObjectSize(FI);
5980 int BFS = MFI->getObjectSize(BFI);
5981 if (FS != BFS || FS != (int)Bytes) return false;
5982 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
5986 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
5987 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
5990 const GlobalValue *GV1 = NULL;
5991 const GlobalValue *GV2 = NULL;
5992 int64_t Offset1 = 0;
5993 int64_t Offset2 = 0;
5994 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
5995 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
5996 if (isGA1 && isGA2 && GV1 == GV2)
5997 return Offset1 == (Offset2 + Dist*Bytes);
6002 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6003 /// it cannot be inferred.
6004 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6005 // If this is a GlobalAddress + cst, return the alignment.
6006 const GlobalValue *GV;
6007 int64_t GVOffset = 0;
6008 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6009 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6010 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6011 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6012 TLI.getTargetData());
6013 unsigned AlignBits = KnownZero.countTrailingOnes();
6014 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6016 return MinAlign(Align, GVOffset);
6019 // If this is a direct reference to a stack slot, use information about the
6020 // stack slot's alignment.
6021 int FrameIdx = 1 << 31;
6022 int64_t FrameOffset = 0;
6023 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6024 FrameIdx = FI->getIndex();
6025 } else if (isBaseWithConstantOffset(Ptr) &&
6026 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6028 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6029 FrameOffset = Ptr.getConstantOperandVal(1);
6032 if (FrameIdx != (1 << 31)) {
6033 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6034 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6042 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6043 unsigned GlobalAddressSDNode::getAddressSpace() const {
6044 return getGlobal()->getType()->getAddressSpace();
6048 Type *ConstantPoolSDNode::getType() const {
6049 if (isMachineConstantPoolEntry())
6050 return Val.MachineCPVal->getType();
6051 return Val.ConstVal->getType();
6054 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6056 unsigned &SplatBitSize,
6058 unsigned MinSplatBits,
6060 EVT VT = getValueType(0);
6061 assert(VT.isVector() && "Expected a vector type");
6062 unsigned sz = VT.getSizeInBits();
6063 if (MinSplatBits > sz)
6066 SplatValue = APInt(sz, 0);
6067 SplatUndef = APInt(sz, 0);
6069 // Get the bits. Bits with undefined values (when the corresponding element
6070 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6071 // in SplatValue. If any of the values are not constant, give up and return
6073 unsigned int nOps = getNumOperands();
6074 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6075 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6077 for (unsigned j = 0; j < nOps; ++j) {
6078 unsigned i = isBigEndian ? nOps-1-j : j;
6079 SDValue OpVal = getOperand(i);
6080 unsigned BitPos = j * EltBitSize;
6082 if (OpVal.getOpcode() == ISD::UNDEF)
6083 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6084 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6085 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6086 zextOrTrunc(sz) << BitPos;
6087 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6088 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6093 // The build_vector is all constants or undefs. Find the smallest element
6094 // size that splats the vector.
6096 HasAnyUndefs = (SplatUndef != 0);
6099 unsigned HalfSize = sz / 2;
6100 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6101 APInt LowValue = SplatValue.trunc(HalfSize);
6102 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6103 APInt LowUndef = SplatUndef.trunc(HalfSize);
6105 // If the two halves do not match (ignoring undef bits), stop here.
6106 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6107 MinSplatBits > HalfSize)
6110 SplatValue = HighValue | LowValue;
6111 SplatUndef = HighUndef & LowUndef;
6120 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6121 // Find the first non-undef value in the shuffle mask.
6123 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6126 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6128 // Make sure all remaining elements are either undef or the same as the first
6130 for (int Idx = Mask[i]; i != e; ++i)
6131 if (Mask[i] >= 0 && Mask[i] != Idx)
6137 static void checkForCyclesHelper(const SDNode *N,
6138 SmallPtrSet<const SDNode*, 32> &Visited,
6139 SmallPtrSet<const SDNode*, 32> &Checked) {
6140 // If this node has already been checked, don't check it again.
6141 if (Checked.count(N))
6144 // If a node has already been visited on this depth-first walk, reject it as
6146 if (!Visited.insert(N)) {
6147 dbgs() << "Offending node:\n";
6149 errs() << "Detected cycle in SelectionDAG\n";
6153 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6154 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6161 void llvm::checkForCycles(const llvm::SDNode *N) {
6163 assert(N && "Checking nonexistant SDNode");
6164 SmallPtrSet<const SDNode*, 32> visited;
6165 SmallPtrSet<const SDNode*, 32> checked;
6166 checkForCyclesHelper(N, visited, checked);
6170 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6171 checkForCycles(DAG->getRoot().getNode());