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);
1971 // All bits are zero except the low bit.
1972 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1976 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1977 // We know that the top bits of C-X are clear if X contains less bits
1978 // than C (i.e. no wrap-around can happen). For example, 20-X is
1979 // positive if we can prove that X is >= 0 and < 16.
1980 if (CLHS->getAPIntValue().isNonNegative()) {
1981 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1982 // NLZ can't be BitWidth with no sign bit
1983 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1984 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1986 // If all of the MaskV bits are known to be zero, then we know the
1987 // output top bits are zero, because we now know that the output is
1989 if ((KnownZero2 & MaskV) == MaskV) {
1990 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1991 // Top bits known zero.
1992 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2000 // Output known-0 bits are known if clear or set in both the low clear bits
2001 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2002 // low 3 bits clear.
2003 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2004 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2005 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2007 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2008 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2009 KnownZeroOut = std::min(KnownZeroOut,
2010 KnownZero2.countTrailingOnes());
2012 if (Op.getOpcode() == ISD::ADD) {
2013 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2017 // With ADDE, a carry bit may be added in, so we can only use this
2018 // information if we know (at least) that the low two bits are clear. We
2019 // then return to the caller that the low bit is unknown but that other bits
2021 if (KnownZeroOut >= 2) // ADDE
2022 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2026 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2027 const APInt &RA = Rem->getAPIntValue().abs();
2028 if (RA.isPowerOf2()) {
2029 APInt LowBits = RA - 1;
2030 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2031 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2033 // The low bits of the first operand are unchanged by the srem.
2034 KnownZero = KnownZero2 & LowBits;
2035 KnownOne = KnownOne2 & LowBits;
2037 // If the first operand is non-negative or has all low bits zero, then
2038 // the upper bits are all zero.
2039 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2040 KnownZero |= ~LowBits;
2042 // If the first operand is negative and not all low bits are zero, then
2043 // the upper bits are all one.
2044 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2045 KnownOne |= ~LowBits;
2046 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2051 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2052 const APInt &RA = Rem->getAPIntValue();
2053 if (RA.isPowerOf2()) {
2054 APInt LowBits = (RA - 1);
2055 KnownZero |= ~LowBits;
2056 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2057 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2062 // Since the result is less than or equal to either operand, any leading
2063 // zero bits in either operand must also exist in the result.
2064 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2065 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2067 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2068 KnownZero2.countLeadingOnes());
2069 KnownOne.clearAllBits();
2070 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2073 case ISD::FrameIndex:
2074 case ISD::TargetFrameIndex:
2075 if (unsigned Align = InferPtrAlignment(Op)) {
2076 // The low bits are known zero if the pointer is aligned.
2077 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2083 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2086 case ISD::INTRINSIC_WO_CHAIN:
2087 case ISD::INTRINSIC_W_CHAIN:
2088 case ISD::INTRINSIC_VOID:
2089 // Allow the target to implement this method for its nodes.
2090 TLI.computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2095 /// ComputeNumSignBits - Return the number of times the sign bit of the
2096 /// register is replicated into the other bits. We know that at least 1 bit
2097 /// is always equal to the sign bit (itself), but other cases can give us
2098 /// information. For example, immediately after an "SRA X, 2", we know that
2099 /// the top 3 bits are all equal to each other, so we return 3.
2100 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2101 EVT VT = Op.getValueType();
2102 assert(VT.isInteger() && "Invalid VT!");
2103 unsigned VTBits = VT.getScalarType().getSizeInBits();
2105 unsigned FirstAnswer = 1;
2108 return 1; // Limit search depth.
2110 switch (Op.getOpcode()) {
2112 case ISD::AssertSext:
2113 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2114 return VTBits-Tmp+1;
2115 case ISD::AssertZext:
2116 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2119 case ISD::Constant: {
2120 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2121 return Val.getNumSignBits();
2124 case ISD::SIGN_EXTEND:
2125 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2126 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2128 case ISD::SIGN_EXTEND_INREG:
2129 // Max of the input and what this extends.
2131 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2134 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2135 return std::max(Tmp, Tmp2);
2138 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2139 // SRA X, C -> adds C sign bits.
2140 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2141 Tmp += C->getZExtValue();
2142 if (Tmp > VTBits) Tmp = VTBits;
2146 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2147 // shl destroys sign bits.
2148 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2149 if (C->getZExtValue() >= VTBits || // Bad shift.
2150 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2151 return Tmp - C->getZExtValue();
2156 case ISD::XOR: // NOT is handled here.
2157 // Logical binary ops preserve the number of sign bits at the worst.
2158 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2160 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2161 FirstAnswer = std::min(Tmp, Tmp2);
2162 // We computed what we know about the sign bits as our first
2163 // answer. Now proceed to the generic code that uses
2164 // ComputeMaskedBits, and pick whichever answer is better.
2169 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2170 if (Tmp == 1) return 1; // Early out.
2171 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2172 return std::min(Tmp, Tmp2);
2180 if (Op.getResNo() != 1)
2182 // The boolean result conforms to getBooleanContents. Fall through.
2184 // If setcc returns 0/-1, all bits are sign bits.
2185 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2186 TargetLowering::ZeroOrNegativeOneBooleanContent)
2191 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2192 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2194 // Handle rotate right by N like a rotate left by 32-N.
2195 if (Op.getOpcode() == ISD::ROTR)
2196 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2198 // If we aren't rotating out all of the known-in sign bits, return the
2199 // number that are left. This handles rotl(sext(x), 1) for example.
2200 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2201 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2205 // Add can have at most one carry bit. Thus we know that the output
2206 // is, at worst, one more bit than the inputs.
2207 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2208 if (Tmp == 1) return 1; // Early out.
2210 // Special case decrementing a value (ADD X, -1):
2211 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2212 if (CRHS->isAllOnesValue()) {
2213 APInt KnownZero, KnownOne;
2214 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2216 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2218 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2221 // If we are subtracting one from a positive number, there is no carry
2222 // out of the result.
2223 if (KnownZero.isNegative())
2227 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2228 if (Tmp2 == 1) return 1;
2229 return std::min(Tmp, Tmp2)-1;
2232 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2233 if (Tmp2 == 1) return 1;
2236 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2237 if (CLHS->isNullValue()) {
2238 APInt KnownZero, KnownOne;
2239 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2240 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2242 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2245 // If the input is known to be positive (the sign bit is known clear),
2246 // the output of the NEG has the same number of sign bits as the input.
2247 if (KnownZero.isNegative())
2250 // Otherwise, we treat this like a SUB.
2253 // Sub can have at most one carry bit. Thus we know that the output
2254 // is, at worst, one more bit than the inputs.
2255 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2256 if (Tmp == 1) return 1; // Early out.
2257 return std::min(Tmp, Tmp2)-1;
2259 // FIXME: it's tricky to do anything useful for this, but it is an important
2260 // case for targets like X86.
2264 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2265 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2266 unsigned ExtType = LD->getExtensionType();
2269 case ISD::SEXTLOAD: // '17' bits known
2270 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2271 return VTBits-Tmp+1;
2272 case ISD::ZEXTLOAD: // '16' bits known
2273 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2278 // Allow the target to implement this method for its nodes.
2279 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2280 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2281 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2282 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2283 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2284 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2287 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2288 // use this information.
2289 APInt KnownZero, KnownOne;
2290 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2293 if (KnownZero.isNegative()) { // sign bit is 0
2295 } else if (KnownOne.isNegative()) { // sign bit is 1;
2302 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2303 // the number of identical bits in the top of the input value.
2305 Mask <<= Mask.getBitWidth()-VTBits;
2306 // Return # leading zeros. We use 'min' here in case Val was zero before
2307 // shifting. We don't want to return '64' as for an i32 "0".
2308 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2311 /// isBaseWithConstantOffset - Return true if the specified operand is an
2312 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2313 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2314 /// semantics as an ADD. This handles the equivalence:
2315 /// X|Cst == X+Cst iff X&Cst = 0.
2316 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2317 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2318 !isa<ConstantSDNode>(Op.getOperand(1)))
2321 if (Op.getOpcode() == ISD::OR &&
2322 !MaskedValueIsZero(Op.getOperand(0),
2323 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2330 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2331 // If we're told that NaNs won't happen, assume they won't.
2332 if (getTarget().Options.NoNaNsFPMath)
2335 // If the value is a constant, we can obviously see if it is a NaN or not.
2336 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2337 return !C->getValueAPF().isNaN();
2339 // TODO: Recognize more cases here.
2344 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2345 // If the value is a constant, we can obviously see if it is a zero or not.
2346 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2347 return !C->isZero();
2349 // TODO: Recognize more cases here.
2350 switch (Op.getOpcode()) {
2353 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2354 return !C->isNullValue();
2361 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2362 // Check the obvious case.
2363 if (A == B) return true;
2365 // For for negative and positive zero.
2366 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2367 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2368 if (CA->isZero() && CB->isZero()) return true;
2370 // Otherwise they may not be equal.
2374 /// getNode - Gets or creates the specified node.
2376 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2377 FoldingSetNodeID ID;
2378 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2380 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2381 return SDValue(E, 0);
2383 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2384 CSEMap.InsertNode(N, IP);
2386 AllNodes.push_back(N);
2390 return SDValue(N, 0);
2393 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2394 EVT VT, SDValue Operand) {
2395 // Constant fold unary operations with an integer constant operand.
2396 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2397 const APInt &Val = C->getAPIntValue();
2400 case ISD::SIGN_EXTEND:
2401 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2402 case ISD::ANY_EXTEND:
2403 case ISD::ZERO_EXTEND:
2405 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2406 case ISD::UINT_TO_FP:
2407 case ISD::SINT_TO_FP: {
2408 // No compile time operations on ppcf128.
2409 if (VT == MVT::ppcf128) break;
2410 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2411 (void)apf.convertFromAPInt(Val,
2412 Opcode==ISD::SINT_TO_FP,
2413 APFloat::rmNearestTiesToEven);
2414 return getConstantFP(apf, VT);
2417 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2418 return getConstantFP(Val.bitsToFloat(), VT);
2419 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2420 return getConstantFP(Val.bitsToDouble(), VT);
2423 return getConstant(Val.byteSwap(), VT);
2425 return getConstant(Val.countPopulation(), VT);
2427 case ISD::CTLZ_ZERO_UNDEF:
2428 return getConstant(Val.countLeadingZeros(), VT);
2430 case ISD::CTTZ_ZERO_UNDEF:
2431 return getConstant(Val.countTrailingZeros(), VT);
2435 // Constant fold unary operations with a floating point constant operand.
2436 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2437 APFloat V = C->getValueAPF(); // make copy
2438 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2442 return getConstantFP(V, VT);
2445 return getConstantFP(V, VT);
2446 case ISD::FP_EXTEND: {
2448 // This can return overflow, underflow, or inexact; we don't care.
2449 // FIXME need to be more flexible about rounding mode.
2450 (void)V.convert(*EVTToAPFloatSemantics(VT),
2451 APFloat::rmNearestTiesToEven, &ignored);
2452 return getConstantFP(V, VT);
2454 case ISD::FP_TO_SINT:
2455 case ISD::FP_TO_UINT: {
2458 assert(integerPartWidth >= 64);
2459 // FIXME need to be more flexible about rounding mode.
2460 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2461 Opcode==ISD::FP_TO_SINT,
2462 APFloat::rmTowardZero, &ignored);
2463 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2465 APInt api(VT.getSizeInBits(), x);
2466 return getConstant(api, VT);
2469 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2470 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2471 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2472 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2478 unsigned OpOpcode = Operand.getNode()->getOpcode();
2480 case ISD::TokenFactor:
2481 case ISD::MERGE_VALUES:
2482 case ISD::CONCAT_VECTORS:
2483 return Operand; // Factor, merge or concat of one node? No need.
2484 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2485 case ISD::FP_EXTEND:
2486 assert(VT.isFloatingPoint() &&
2487 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2488 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2489 assert((!VT.isVector() ||
2490 VT.getVectorNumElements() ==
2491 Operand.getValueType().getVectorNumElements()) &&
2492 "Vector element count mismatch!");
2493 if (Operand.getOpcode() == ISD::UNDEF)
2494 return getUNDEF(VT);
2496 case ISD::SIGN_EXTEND:
2497 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2498 "Invalid SIGN_EXTEND!");
2499 if (Operand.getValueType() == VT) return Operand; // noop extension
2500 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2501 "Invalid sext node, dst < src!");
2502 assert((!VT.isVector() ||
2503 VT.getVectorNumElements() ==
2504 Operand.getValueType().getVectorNumElements()) &&
2505 "Vector element count mismatch!");
2506 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2507 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2508 else if (OpOpcode == ISD::UNDEF)
2509 // sext(undef) = 0, because the top bits will all be the same.
2510 return getConstant(0, VT);
2512 case ISD::ZERO_EXTEND:
2513 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2514 "Invalid ZERO_EXTEND!");
2515 if (Operand.getValueType() == VT) return Operand; // noop extension
2516 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2517 "Invalid zext node, dst < src!");
2518 assert((!VT.isVector() ||
2519 VT.getVectorNumElements() ==
2520 Operand.getValueType().getVectorNumElements()) &&
2521 "Vector element count mismatch!");
2522 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2523 return getNode(ISD::ZERO_EXTEND, DL, VT,
2524 Operand.getNode()->getOperand(0));
2525 else if (OpOpcode == ISD::UNDEF)
2526 // zext(undef) = 0, because the top bits will be zero.
2527 return getConstant(0, VT);
2529 case ISD::ANY_EXTEND:
2530 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2531 "Invalid ANY_EXTEND!");
2532 if (Operand.getValueType() == VT) return Operand; // noop extension
2533 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2534 "Invalid anyext node, dst < src!");
2535 assert((!VT.isVector() ||
2536 VT.getVectorNumElements() ==
2537 Operand.getValueType().getVectorNumElements()) &&
2538 "Vector element count mismatch!");
2540 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2541 OpOpcode == ISD::ANY_EXTEND)
2542 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2543 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2544 else if (OpOpcode == ISD::UNDEF)
2545 return getUNDEF(VT);
2547 // (ext (trunx x)) -> x
2548 if (OpOpcode == ISD::TRUNCATE) {
2549 SDValue OpOp = Operand.getNode()->getOperand(0);
2550 if (OpOp.getValueType() == VT)
2555 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2556 "Invalid TRUNCATE!");
2557 if (Operand.getValueType() == VT) return Operand; // noop truncate
2558 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2559 "Invalid truncate node, src < dst!");
2560 assert((!VT.isVector() ||
2561 VT.getVectorNumElements() ==
2562 Operand.getValueType().getVectorNumElements()) &&
2563 "Vector element count mismatch!");
2564 if (OpOpcode == ISD::TRUNCATE)
2565 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2566 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2567 OpOpcode == ISD::ANY_EXTEND) {
2568 // If the source is smaller than the dest, we still need an extend.
2569 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2570 .bitsLT(VT.getScalarType()))
2571 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2572 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2573 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2574 return Operand.getNode()->getOperand(0);
2576 if (OpOpcode == ISD::UNDEF)
2577 return getUNDEF(VT);
2580 // Basic sanity checking.
2581 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2582 && "Cannot BITCAST between types of different sizes!");
2583 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2584 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2585 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2586 if (OpOpcode == ISD::UNDEF)
2587 return getUNDEF(VT);
2589 case ISD::SCALAR_TO_VECTOR:
2590 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2591 (VT.getVectorElementType() == Operand.getValueType() ||
2592 (VT.getVectorElementType().isInteger() &&
2593 Operand.getValueType().isInteger() &&
2594 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2595 "Illegal SCALAR_TO_VECTOR node!");
2596 if (OpOpcode == ISD::UNDEF)
2597 return getUNDEF(VT);
2598 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2599 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2600 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2601 Operand.getConstantOperandVal(1) == 0 &&
2602 Operand.getOperand(0).getValueType() == VT)
2603 return Operand.getOperand(0);
2606 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2607 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2608 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2609 Operand.getNode()->getOperand(0));
2610 if (OpOpcode == ISD::FNEG) // --X -> X
2611 return Operand.getNode()->getOperand(0);
2614 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2615 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2620 SDVTList VTs = getVTList(VT);
2621 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2622 FoldingSetNodeID ID;
2623 SDValue Ops[1] = { Operand };
2624 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2626 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2627 return SDValue(E, 0);
2629 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2630 CSEMap.InsertNode(N, IP);
2632 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2635 AllNodes.push_back(N);
2639 return SDValue(N, 0);
2642 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2644 ConstantSDNode *Cst1,
2645 ConstantSDNode *Cst2) {
2646 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2649 case ISD::ADD: return getConstant(C1 + C2, VT);
2650 case ISD::SUB: return getConstant(C1 - C2, VT);
2651 case ISD::MUL: return getConstant(C1 * C2, VT);
2653 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2656 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2659 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2662 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2664 case ISD::AND: return getConstant(C1 & C2, VT);
2665 case ISD::OR: return getConstant(C1 | C2, VT);
2666 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2667 case ISD::SHL: return getConstant(C1 << C2, VT);
2668 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2669 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2670 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2671 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2678 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2679 SDValue N1, SDValue N2) {
2680 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2681 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2684 case ISD::TokenFactor:
2685 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2686 N2.getValueType() == MVT::Other && "Invalid token factor!");
2687 // Fold trivial token factors.
2688 if (N1.getOpcode() == ISD::EntryToken) return N2;
2689 if (N2.getOpcode() == ISD::EntryToken) return N1;
2690 if (N1 == N2) return N1;
2692 case ISD::CONCAT_VECTORS:
2693 // Concat of UNDEFs is UNDEF.
2694 if (N1.getOpcode() == ISD::UNDEF &&
2695 N2.getOpcode() == ISD::UNDEF)
2696 return getUNDEF(VT);
2698 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2699 // one big BUILD_VECTOR.
2700 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2701 N2.getOpcode() == ISD::BUILD_VECTOR) {
2702 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2703 N1.getNode()->op_end());
2704 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2705 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2709 assert(VT.isInteger() && "This operator does not apply to FP types!");
2710 assert(N1.getValueType() == N2.getValueType() &&
2711 N1.getValueType() == VT && "Binary operator types must match!");
2712 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2713 // worth handling here.
2714 if (N2C && N2C->isNullValue())
2716 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2723 assert(VT.isInteger() && "This operator does not apply to FP types!");
2724 assert(N1.getValueType() == N2.getValueType() &&
2725 N1.getValueType() == VT && "Binary operator types must match!");
2726 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2727 // it's worth handling here.
2728 if (N2C && N2C->isNullValue())
2738 assert(VT.isInteger() && "This operator does not apply to FP types!");
2739 assert(N1.getValueType() == N2.getValueType() &&
2740 N1.getValueType() == VT && "Binary operator types must match!");
2747 if (getTarget().Options.UnsafeFPMath) {
2748 if (Opcode == ISD::FADD) {
2750 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2751 if (CFP->getValueAPF().isZero())
2754 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2755 if (CFP->getValueAPF().isZero())
2757 } else if (Opcode == ISD::FSUB) {
2759 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2760 if (CFP->getValueAPF().isZero())
2764 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2765 assert(N1.getValueType() == N2.getValueType() &&
2766 N1.getValueType() == VT && "Binary operator types must match!");
2768 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2769 assert(N1.getValueType() == VT &&
2770 N1.getValueType().isFloatingPoint() &&
2771 N2.getValueType().isFloatingPoint() &&
2772 "Invalid FCOPYSIGN!");
2779 assert(VT == N1.getValueType() &&
2780 "Shift operators return type must be the same as their first arg");
2781 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2782 "Shifts only work on integers");
2783 // Verify that the shift amount VT is bit enough to hold valid shift
2784 // amounts. This catches things like trying to shift an i1024 value by an
2785 // i8, which is easy to fall into in generic code that uses
2786 // TLI.getShiftAmount().
2787 assert(N2.getValueType().getSizeInBits() >=
2788 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2789 "Invalid use of small shift amount with oversized value!");
2791 // Always fold shifts of i1 values so the code generator doesn't need to
2792 // handle them. Since we know the size of the shift has to be less than the
2793 // size of the value, the shift/rotate count is guaranteed to be zero.
2796 if (N2C && N2C->isNullValue())
2799 case ISD::FP_ROUND_INREG: {
2800 EVT EVT = cast<VTSDNode>(N2)->getVT();
2801 assert(VT == N1.getValueType() && "Not an inreg round!");
2802 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2803 "Cannot FP_ROUND_INREG integer types");
2804 assert(EVT.isVector() == VT.isVector() &&
2805 "FP_ROUND_INREG type should be vector iff the operand "
2807 assert((!EVT.isVector() ||
2808 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2809 "Vector element counts must match in FP_ROUND_INREG");
2810 assert(EVT.bitsLE(VT) && "Not rounding down!");
2812 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2816 assert(VT.isFloatingPoint() &&
2817 N1.getValueType().isFloatingPoint() &&
2818 VT.bitsLE(N1.getValueType()) &&
2819 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2820 if (N1.getValueType() == VT) return N1; // noop conversion.
2822 case ISD::AssertSext:
2823 case ISD::AssertZext: {
2824 EVT EVT = cast<VTSDNode>(N2)->getVT();
2825 assert(VT == N1.getValueType() && "Not an inreg extend!");
2826 assert(VT.isInteger() && EVT.isInteger() &&
2827 "Cannot *_EXTEND_INREG FP types");
2828 assert(!EVT.isVector() &&
2829 "AssertSExt/AssertZExt type should be the vector element type "
2830 "rather than the vector type!");
2831 assert(EVT.bitsLE(VT) && "Not extending!");
2832 if (VT == EVT) return N1; // noop assertion.
2835 case ISD::SIGN_EXTEND_INREG: {
2836 EVT EVT = cast<VTSDNode>(N2)->getVT();
2837 assert(VT == N1.getValueType() && "Not an inreg extend!");
2838 assert(VT.isInteger() && EVT.isInteger() &&
2839 "Cannot *_EXTEND_INREG FP types");
2840 assert(EVT.isVector() == VT.isVector() &&
2841 "SIGN_EXTEND_INREG type should be vector iff the operand "
2843 assert((!EVT.isVector() ||
2844 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2845 "Vector element counts must match in SIGN_EXTEND_INREG");
2846 assert(EVT.bitsLE(VT) && "Not extending!");
2847 if (EVT == VT) return N1; // Not actually extending
2850 APInt Val = N1C->getAPIntValue();
2851 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2852 Val <<= Val.getBitWidth()-FromBits;
2853 Val = Val.ashr(Val.getBitWidth()-FromBits);
2854 return getConstant(Val, VT);
2858 case ISD::EXTRACT_VECTOR_ELT:
2859 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2860 if (N1.getOpcode() == ISD::UNDEF)
2861 return getUNDEF(VT);
2863 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2864 // expanding copies of large vectors from registers.
2866 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2867 N1.getNumOperands() > 0) {
2869 N1.getOperand(0).getValueType().getVectorNumElements();
2870 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2871 N1.getOperand(N2C->getZExtValue() / Factor),
2872 getConstant(N2C->getZExtValue() % Factor,
2873 N2.getValueType()));
2876 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2877 // expanding large vector constants.
2878 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2879 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2880 EVT VEltTy = N1.getValueType().getVectorElementType();
2881 if (Elt.getValueType() != VEltTy) {
2882 // If the vector element type is not legal, the BUILD_VECTOR operands
2883 // are promoted and implicitly truncated. Make that explicit here.
2884 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt);
2887 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT
2888 // result is implicitly extended.
2889 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt);
2894 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2895 // operations are lowered to scalars.
2896 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2897 // If the indices are the same, return the inserted element else
2898 // if the indices are known different, extract the element from
2899 // the original vector.
2900 SDValue N1Op2 = N1.getOperand(2);
2901 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2903 if (N1Op2C && N2C) {
2904 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2905 if (VT == N1.getOperand(1).getValueType())
2906 return N1.getOperand(1);
2908 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2911 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2915 case ISD::EXTRACT_ELEMENT:
2916 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2917 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2918 (N1.getValueType().isInteger() == VT.isInteger()) &&
2919 N1.getValueType() != VT &&
2920 "Wrong types for EXTRACT_ELEMENT!");
2922 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2923 // 64-bit integers into 32-bit parts. Instead of building the extract of
2924 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2925 if (N1.getOpcode() == ISD::BUILD_PAIR)
2926 return N1.getOperand(N2C->getZExtValue());
2928 // EXTRACT_ELEMENT of a constant int is also very common.
2929 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2930 unsigned ElementSize = VT.getSizeInBits();
2931 unsigned Shift = ElementSize * N2C->getZExtValue();
2932 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2933 return getConstant(ShiftedVal.trunc(ElementSize), VT);
2936 case ISD::EXTRACT_SUBVECTOR: {
2938 if (VT.isSimple() && N1.getValueType().isSimple()) {
2939 assert(VT.isVector() && N1.getValueType().isVector() &&
2940 "Extract subvector VTs must be a vectors!");
2941 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
2942 "Extract subvector VTs must have the same element type!");
2943 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
2944 "Extract subvector must be from larger vector to smaller vector!");
2946 if (isa<ConstantSDNode>(Index.getNode())) {
2947 assert((VT.getVectorNumElements() +
2948 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
2949 <= N1.getValueType().getVectorNumElements())
2950 && "Extract subvector overflow!");
2953 // Trivial extraction.
2954 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
2963 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
2964 if (SV.getNode()) return SV;
2965 } else { // Cannonicalize constant to RHS if commutative
2966 if (isCommutativeBinOp(Opcode)) {
2967 std::swap(N1C, N2C);
2973 // Constant fold FP operations.
2974 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
2975 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
2977 if (!N2CFP && isCommutativeBinOp(Opcode)) {
2978 // Cannonicalize constant to RHS if commutative
2979 std::swap(N1CFP, N2CFP);
2981 } else if (N2CFP && VT != MVT::ppcf128) {
2982 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2983 APFloat::opStatus s;
2986 s = V1.add(V2, APFloat::rmNearestTiesToEven);
2987 if (s != APFloat::opInvalidOp)
2988 return getConstantFP(V1, VT);
2991 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2992 if (s!=APFloat::opInvalidOp)
2993 return getConstantFP(V1, VT);
2996 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2997 if (s!=APFloat::opInvalidOp)
2998 return getConstantFP(V1, VT);
3001 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3002 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3003 return getConstantFP(V1, VT);
3006 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3007 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3008 return getConstantFP(V1, VT);
3010 case ISD::FCOPYSIGN:
3012 return getConstantFP(V1, VT);
3017 if (Opcode == ISD::FP_ROUND) {
3018 APFloat V = N1CFP->getValueAPF(); // make copy
3020 // This can return overflow, underflow, or inexact; we don't care.
3021 // FIXME need to be more flexible about rounding mode.
3022 (void)V.convert(*EVTToAPFloatSemantics(VT),
3023 APFloat::rmNearestTiesToEven, &ignored);
3024 return getConstantFP(V, VT);
3028 // Canonicalize an UNDEF to the RHS, even over a constant.
3029 if (N1.getOpcode() == ISD::UNDEF) {
3030 if (isCommutativeBinOp(Opcode)) {
3034 case ISD::FP_ROUND_INREG:
3035 case ISD::SIGN_EXTEND_INREG:
3041 return N1; // fold op(undef, arg2) -> undef
3049 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3050 // For vectors, we can't easily build an all zero vector, just return
3057 // Fold a bunch of operators when the RHS is undef.
3058 if (N2.getOpcode() == ISD::UNDEF) {
3061 if (N1.getOpcode() == ISD::UNDEF)
3062 // Handle undef ^ undef -> 0 special case. This is a common
3064 return getConstant(0, VT);
3074 return N2; // fold op(arg1, undef) -> undef
3080 if (getTarget().Options.UnsafeFPMath)
3088 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3089 // For vectors, we can't easily build an all zero vector, just return
3094 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3095 // For vectors, we can't easily build an all one vector, just return
3103 // Memoize this node if possible.
3105 SDVTList VTs = getVTList(VT);
3106 if (VT != MVT::Glue) {
3107 SDValue Ops[] = { N1, N2 };
3108 FoldingSetNodeID ID;
3109 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3111 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3112 return SDValue(E, 0);
3114 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3115 CSEMap.InsertNode(N, IP);
3117 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3120 AllNodes.push_back(N);
3124 return SDValue(N, 0);
3127 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3128 SDValue N1, SDValue N2, SDValue N3) {
3129 // Perform various simplifications.
3130 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3132 case ISD::CONCAT_VECTORS:
3133 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3134 // one big BUILD_VECTOR.
3135 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3136 N2.getOpcode() == ISD::BUILD_VECTOR &&
3137 N3.getOpcode() == ISD::BUILD_VECTOR) {
3138 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3139 N1.getNode()->op_end());
3140 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3141 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3142 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3146 // Use FoldSetCC to simplify SETCC's.
3147 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3148 if (Simp.getNode()) return Simp;
3153 if (N1C->getZExtValue())
3154 return N2; // select true, X, Y -> X
3155 return N3; // select false, X, Y -> Y
3158 if (N2 == N3) return N2; // select C, X, X -> X
3160 case ISD::VECTOR_SHUFFLE:
3161 llvm_unreachable("should use getVectorShuffle constructor!");
3162 case ISD::INSERT_SUBVECTOR: {
3164 if (VT.isSimple() && N1.getValueType().isSimple()
3165 && N2.getValueType().isSimple()) {
3166 assert(VT.isVector() && N1.getValueType().isVector() &&
3167 N2.getValueType().isVector() &&
3168 "Insert subvector VTs must be a vectors");
3169 assert(VT == N1.getValueType() &&
3170 "Dest and insert subvector source types must match!");
3171 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3172 "Insert subvector must be from smaller vector to larger vector!");
3173 if (isa<ConstantSDNode>(Index.getNode())) {
3174 assert((N2.getValueType().getVectorNumElements() +
3175 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3176 <= VT.getVectorNumElements())
3177 && "Insert subvector overflow!");
3180 // Trivial insertion.
3181 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3187 // Fold bit_convert nodes from a type to themselves.
3188 if (N1.getValueType() == VT)
3193 // Memoize node if it doesn't produce a flag.
3195 SDVTList VTs = getVTList(VT);
3196 if (VT != MVT::Glue) {
3197 SDValue Ops[] = { N1, N2, N3 };
3198 FoldingSetNodeID ID;
3199 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3201 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3202 return SDValue(E, 0);
3204 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3205 CSEMap.InsertNode(N, IP);
3207 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3210 AllNodes.push_back(N);
3214 return SDValue(N, 0);
3217 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3218 SDValue N1, SDValue N2, SDValue N3,
3220 SDValue Ops[] = { N1, N2, N3, N4 };
3221 return getNode(Opcode, DL, VT, Ops, 4);
3224 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3225 SDValue N1, SDValue N2, SDValue N3,
3226 SDValue N4, SDValue N5) {
3227 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3228 return getNode(Opcode, DL, VT, Ops, 5);
3231 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3232 /// the incoming stack arguments to be loaded from the stack.
3233 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3234 SmallVector<SDValue, 8> ArgChains;
3236 // Include the original chain at the beginning of the list. When this is
3237 // used by target LowerCall hooks, this helps legalize find the
3238 // CALLSEQ_BEGIN node.
3239 ArgChains.push_back(Chain);
3241 // Add a chain value for each stack argument.
3242 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3243 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3244 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3245 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3246 if (FI->getIndex() < 0)
3247 ArgChains.push_back(SDValue(L, 1));
3249 // Build a tokenfactor for all the chains.
3250 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3251 &ArgChains[0], ArgChains.size());
3254 /// SplatByte - Distribute ByteVal over NumBits bits.
3255 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3256 APInt Val = APInt(NumBits, ByteVal);
3258 for (unsigned i = NumBits; i > 8; i >>= 1) {
3259 Val = (Val << Shift) | Val;
3265 /// getMemsetValue - Vectorized representation of the memset value
3267 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3269 assert(Value.getOpcode() != ISD::UNDEF);
3271 unsigned NumBits = VT.getScalarType().getSizeInBits();
3272 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3273 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3275 return DAG.getConstant(Val, VT);
3276 return DAG.getConstantFP(APFloat(Val), VT);
3279 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3281 // Use a multiplication with 0x010101... to extend the input to the
3283 APInt Magic = SplatByte(NumBits, 0x01);
3284 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3290 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3291 /// used when a memcpy is turned into a memset when the source is a constant
3293 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3294 const TargetLowering &TLI, StringRef Str) {
3295 // Handle vector with all elements zero.
3298 return DAG.getConstant(0, VT);
3299 else if (VT == MVT::f32 || VT == MVT::f64)
3300 return DAG.getConstantFP(0.0, VT);
3301 else if (VT.isVector()) {
3302 unsigned NumElts = VT.getVectorNumElements();
3303 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3304 return DAG.getNode(ISD::BITCAST, dl, VT,
3305 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3308 llvm_unreachable("Expected type!");
3311 assert(!VT.isVector() && "Can't handle vector type here!");
3312 unsigned NumVTBytes = VT.getSizeInBits() / 8;
3313 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3316 if (TLI.isLittleEndian()) {
3317 for (unsigned i = 0; i != NumBytes; ++i)
3318 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3320 for (unsigned i = 0; i != NumBytes; ++i)
3321 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3324 return DAG.getConstant(Val, VT);
3327 /// getMemBasePlusOffset - Returns base and offset node for the
3329 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3330 SelectionDAG &DAG) {
3331 EVT VT = Base.getValueType();
3332 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3333 VT, Base, DAG.getConstant(Offset, VT));
3336 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3338 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3339 unsigned SrcDelta = 0;
3340 GlobalAddressSDNode *G = NULL;
3341 if (Src.getOpcode() == ISD::GlobalAddress)
3342 G = cast<GlobalAddressSDNode>(Src);
3343 else if (Src.getOpcode() == ISD::ADD &&
3344 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3345 Src.getOperand(1).getOpcode() == ISD::Constant) {
3346 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3347 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3352 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3355 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3356 /// to replace the memset / memcpy. Return true if the number of memory ops
3357 /// is below the threshold. It returns the types of the sequence of
3358 /// memory ops to perform memset / memcpy by reference.
3359 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3360 unsigned Limit, uint64_t Size,
3361 unsigned DstAlign, unsigned SrcAlign,
3365 const TargetLowering &TLI) {
3366 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3367 "Expecting memcpy / memset source to meet alignment requirement!");
3368 // If 'SrcAlign' is zero, that means the memory operation does not need to
3369 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3370 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3371 // is the specified alignment of the memory operation. If it is zero, that
3372 // means it's possible to change the alignment of the destination.
3373 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3374 // not need to be loaded.
3375 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3376 IsZeroVal, MemcpyStrSrc,
3377 DAG.getMachineFunction());
3379 if (VT == MVT::Other) {
3380 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3381 TLI.allowsUnalignedMemoryAccesses(VT)) {
3382 VT = TLI.getPointerTy();
3384 switch (DstAlign & 7) {
3385 case 0: VT = MVT::i64; break;
3386 case 4: VT = MVT::i32; break;
3387 case 2: VT = MVT::i16; break;
3388 default: VT = MVT::i8; break;
3393 while (!TLI.isTypeLegal(LVT))
3394 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3395 assert(LVT.isInteger());
3401 unsigned NumMemOps = 0;
3403 unsigned VTSize = VT.getSizeInBits() / 8;
3404 while (VTSize > Size) {
3405 // For now, only use non-vector load / store's for the left-over pieces.
3406 if (VT.isVector() || VT.isFloatingPoint()) {
3408 while (!TLI.isTypeLegal(VT))
3409 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3410 VTSize = VT.getSizeInBits() / 8;
3412 // This can result in a type that is not legal on the target, e.g.
3413 // 1 or 2 bytes on PPC.
3414 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3419 if (++NumMemOps > Limit)
3421 MemOps.push_back(VT);
3428 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3429 SDValue Chain, SDValue Dst,
3430 SDValue Src, uint64_t Size,
3431 unsigned Align, bool isVol,
3433 MachinePointerInfo DstPtrInfo,
3434 MachinePointerInfo SrcPtrInfo) {
3435 // Turn a memcpy of undef to nop.
3436 if (Src.getOpcode() == ISD::UNDEF)
3439 // Expand memcpy to a series of load and store ops if the size operand falls
3440 // below a certain threshold.
3441 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3442 // rather than maybe a humongous number of loads and stores.
3443 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3444 std::vector<EVT> MemOps;
3445 bool DstAlignCanChange = false;
3446 MachineFunction &MF = DAG.getMachineFunction();
3447 MachineFrameInfo *MFI = MF.getFrameInfo();
3448 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3449 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3450 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3451 DstAlignCanChange = true;
3452 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3453 if (Align > SrcAlign)
3456 bool CopyFromStr = isMemSrcFromString(Src, Str);
3457 bool isZeroStr = CopyFromStr && Str.empty();
3458 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3460 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3461 (DstAlignCanChange ? 0 : Align),
3462 (isZeroStr ? 0 : SrcAlign),
3463 true, CopyFromStr, DAG, TLI))
3466 if (DstAlignCanChange) {
3467 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3468 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3469 if (NewAlign > Align) {
3470 // Give the stack frame object a larger alignment if needed.
3471 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3472 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3477 SmallVector<SDValue, 8> OutChains;
3478 unsigned NumMemOps = MemOps.size();
3479 uint64_t SrcOff = 0, DstOff = 0;
3480 for (unsigned i = 0; i != NumMemOps; ++i) {
3482 unsigned VTSize = VT.getSizeInBits() / 8;
3483 SDValue Value, Store;
3486 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3487 // It's unlikely a store of a vector immediate can be done in a single
3488 // instruction. It would require a load from a constantpool first.
3489 // We only handle zero vectors here.
3490 // FIXME: Handle other cases where store of vector immediate is done in
3491 // a single instruction.
3492 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3493 Store = DAG.getStore(Chain, dl, Value,
3494 getMemBasePlusOffset(Dst, DstOff, DAG),
3495 DstPtrInfo.getWithOffset(DstOff), isVol,
3498 // The type might not be legal for the target. This should only happen
3499 // if the type is smaller than a legal type, as on PPC, so the right
3500 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3501 // to Load/Store if NVT==VT.
3502 // FIXME does the case above also need this?
3503 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3504 assert(NVT.bitsGE(VT));
3505 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3506 getMemBasePlusOffset(Src, SrcOff, DAG),
3507 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3508 MinAlign(SrcAlign, SrcOff));
3509 Store = DAG.getTruncStore(Chain, dl, Value,
3510 getMemBasePlusOffset(Dst, DstOff, DAG),
3511 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3514 OutChains.push_back(Store);
3519 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3520 &OutChains[0], OutChains.size());
3523 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3524 SDValue Chain, SDValue Dst,
3525 SDValue Src, uint64_t Size,
3526 unsigned Align, bool isVol,
3528 MachinePointerInfo DstPtrInfo,
3529 MachinePointerInfo SrcPtrInfo) {
3530 // Turn a memmove of undef to nop.
3531 if (Src.getOpcode() == ISD::UNDEF)
3534 // Expand memmove to a series of load and store ops if the size operand falls
3535 // below a certain threshold.
3536 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3537 std::vector<EVT> MemOps;
3538 bool DstAlignCanChange = false;
3539 MachineFunction &MF = DAG.getMachineFunction();
3540 MachineFrameInfo *MFI = MF.getFrameInfo();
3541 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3542 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3543 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3544 DstAlignCanChange = true;
3545 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3546 if (Align > SrcAlign)
3548 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3550 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3551 (DstAlignCanChange ? 0 : Align),
3552 SrcAlign, true, false, DAG, TLI))
3555 if (DstAlignCanChange) {
3556 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3557 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3558 if (NewAlign > Align) {
3559 // Give the stack frame object a larger alignment if needed.
3560 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3561 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3566 uint64_t SrcOff = 0, DstOff = 0;
3567 SmallVector<SDValue, 8> LoadValues;
3568 SmallVector<SDValue, 8> LoadChains;
3569 SmallVector<SDValue, 8> OutChains;
3570 unsigned NumMemOps = MemOps.size();
3571 for (unsigned i = 0; i < NumMemOps; i++) {
3573 unsigned VTSize = VT.getSizeInBits() / 8;
3574 SDValue Value, Store;
3576 Value = DAG.getLoad(VT, dl, Chain,
3577 getMemBasePlusOffset(Src, SrcOff, DAG),
3578 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3579 false, false, SrcAlign);
3580 LoadValues.push_back(Value);
3581 LoadChains.push_back(Value.getValue(1));
3584 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3585 &LoadChains[0], LoadChains.size());
3587 for (unsigned i = 0; i < NumMemOps; i++) {
3589 unsigned VTSize = VT.getSizeInBits() / 8;
3590 SDValue Value, Store;
3592 Store = DAG.getStore(Chain, dl, LoadValues[i],
3593 getMemBasePlusOffset(Dst, DstOff, DAG),
3594 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3595 OutChains.push_back(Store);
3599 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3600 &OutChains[0], OutChains.size());
3603 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3604 SDValue Chain, SDValue Dst,
3605 SDValue Src, uint64_t Size,
3606 unsigned Align, bool isVol,
3607 MachinePointerInfo DstPtrInfo) {
3608 // Turn a memset of undef to nop.
3609 if (Src.getOpcode() == ISD::UNDEF)
3612 // Expand memset to a series of load/store ops if the size operand
3613 // falls below a certain threshold.
3614 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3615 std::vector<EVT> MemOps;
3616 bool DstAlignCanChange = false;
3617 MachineFunction &MF = DAG.getMachineFunction();
3618 MachineFrameInfo *MFI = MF.getFrameInfo();
3619 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3620 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3621 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3622 DstAlignCanChange = true;
3624 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3625 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3626 Size, (DstAlignCanChange ? 0 : Align), 0,
3627 IsZeroVal, false, DAG, TLI))
3630 if (DstAlignCanChange) {
3631 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3632 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3633 if (NewAlign > Align) {
3634 // Give the stack frame object a larger alignment if needed.
3635 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3636 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3641 SmallVector<SDValue, 8> OutChains;
3642 uint64_t DstOff = 0;
3643 unsigned NumMemOps = MemOps.size();
3645 // Find the largest store and generate the bit pattern for it.
3646 EVT LargestVT = MemOps[0];
3647 for (unsigned i = 1; i < NumMemOps; i++)
3648 if (MemOps[i].bitsGT(LargestVT))
3649 LargestVT = MemOps[i];
3650 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3652 for (unsigned i = 0; i < NumMemOps; i++) {
3655 // If this store is smaller than the largest store see whether we can get
3656 // the smaller value for free with a truncate.
3657 SDValue Value = MemSetValue;
3658 if (VT.bitsLT(LargestVT)) {
3659 if (!LargestVT.isVector() && !VT.isVector() &&
3660 TLI.isTruncateFree(LargestVT, VT))
3661 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3663 Value = getMemsetValue(Src, VT, DAG, dl);
3665 assert(Value.getValueType() == VT && "Value with wrong type.");
3666 SDValue Store = DAG.getStore(Chain, dl, Value,
3667 getMemBasePlusOffset(Dst, DstOff, DAG),
3668 DstPtrInfo.getWithOffset(DstOff),
3669 isVol, false, Align);
3670 OutChains.push_back(Store);
3671 DstOff += VT.getSizeInBits() / 8;
3674 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3675 &OutChains[0], OutChains.size());
3678 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3679 SDValue Src, SDValue Size,
3680 unsigned Align, bool isVol, bool AlwaysInline,
3681 MachinePointerInfo DstPtrInfo,
3682 MachinePointerInfo SrcPtrInfo) {
3684 // Check to see if we should lower the memcpy to loads and stores first.
3685 // For cases within the target-specified limits, this is the best choice.
3686 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3688 // Memcpy with size zero? Just return the original chain.
3689 if (ConstantSize->isNullValue())
3692 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3693 ConstantSize->getZExtValue(),Align,
3694 isVol, false, DstPtrInfo, SrcPtrInfo);
3695 if (Result.getNode())
3699 // Then check to see if we should lower the memcpy with target-specific
3700 // code. If the target chooses to do this, this is the next best.
3702 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3703 isVol, AlwaysInline,
3704 DstPtrInfo, SrcPtrInfo);
3705 if (Result.getNode())
3708 // If we really need inline code and the target declined to provide it,
3709 // use a (potentially long) sequence of loads and stores.
3711 assert(ConstantSize && "AlwaysInline requires a constant size!");
3712 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3713 ConstantSize->getZExtValue(), Align, isVol,
3714 true, DstPtrInfo, SrcPtrInfo);
3717 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3718 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3719 // respect volatile, so they may do things like read or write memory
3720 // beyond the given memory regions. But fixing this isn't easy, and most
3721 // people don't care.
3723 // Emit a library call.
3724 TargetLowering::ArgListTy Args;
3725 TargetLowering::ArgListEntry Entry;
3726 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3727 Entry.Node = Dst; Args.push_back(Entry);
3728 Entry.Node = Src; Args.push_back(Entry);
3729 Entry.Node = Size; Args.push_back(Entry);
3730 // FIXME: pass in DebugLoc
3732 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3733 false, false, false, false, 0,
3734 TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3735 /*isTailCall=*/false,
3736 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3737 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3738 TLI.getPointerTy()),
3740 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3742 return CallResult.second;
3745 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3746 SDValue Src, SDValue Size,
3747 unsigned Align, bool isVol,
3748 MachinePointerInfo DstPtrInfo,
3749 MachinePointerInfo SrcPtrInfo) {
3751 // Check to see if we should lower the memmove to loads and stores first.
3752 // For cases within the target-specified limits, this is the best choice.
3753 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3755 // Memmove with size zero? Just return the original chain.
3756 if (ConstantSize->isNullValue())
3760 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3761 ConstantSize->getZExtValue(), Align, isVol,
3762 false, DstPtrInfo, SrcPtrInfo);
3763 if (Result.getNode())
3767 // Then check to see if we should lower the memmove with target-specific
3768 // code. If the target chooses to do this, this is the next best.
3770 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3771 DstPtrInfo, SrcPtrInfo);
3772 if (Result.getNode())
3775 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3776 // not be safe. See memcpy above for more details.
3778 // Emit a library call.
3779 TargetLowering::ArgListTy Args;
3780 TargetLowering::ArgListEntry Entry;
3781 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3782 Entry.Node = Dst; Args.push_back(Entry);
3783 Entry.Node = Src; Args.push_back(Entry);
3784 Entry.Node = Size; Args.push_back(Entry);
3785 // FIXME: pass in DebugLoc
3787 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3788 false, false, false, false, 0,
3789 TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3790 /*isTailCall=*/false,
3791 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3792 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3793 TLI.getPointerTy()),
3795 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3797 return CallResult.second;
3800 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3801 SDValue Src, SDValue Size,
3802 unsigned Align, bool isVol,
3803 MachinePointerInfo DstPtrInfo) {
3805 // Check to see if we should lower the memset to stores first.
3806 // For cases within the target-specified limits, this is the best choice.
3807 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3809 // Memset with size zero? Just return the original chain.
3810 if (ConstantSize->isNullValue())
3814 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3815 Align, isVol, DstPtrInfo);
3817 if (Result.getNode())
3821 // Then check to see if we should lower the memset with target-specific
3822 // code. If the target chooses to do this, this is the next best.
3824 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3826 if (Result.getNode())
3829 // Emit a library call.
3830 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3831 TargetLowering::ArgListTy Args;
3832 TargetLowering::ArgListEntry Entry;
3833 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3834 Args.push_back(Entry);
3835 // Extend or truncate the argument to be an i32 value for the call.
3836 if (Src.getValueType().bitsGT(MVT::i32))
3837 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3839 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3841 Entry.Ty = Type::getInt32Ty(*getContext());
3842 Entry.isSExt = true;
3843 Args.push_back(Entry);
3845 Entry.Ty = IntPtrTy;
3846 Entry.isSExt = false;
3847 Args.push_back(Entry);
3848 // FIXME: pass in DebugLoc
3850 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3851 false, false, false, false, 0,
3852 TLI.getLibcallCallingConv(RTLIB::MEMSET),
3853 /*isTailCall=*/false,
3854 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3855 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3856 TLI.getPointerTy()),
3858 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3860 return CallResult.second;
3863 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3864 SDValue Chain, SDValue Ptr, SDValue Cmp,
3865 SDValue Swp, MachinePointerInfo PtrInfo,
3867 AtomicOrdering Ordering,
3868 SynchronizationScope SynchScope) {
3869 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3870 Alignment = getEVTAlignment(MemVT);
3872 MachineFunction &MF = getMachineFunction();
3873 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
3875 // For now, atomics are considered to be volatile always.
3876 // FIXME: Volatile isn't really correct; we should keep track of atomic
3877 // orderings in the memoperand.
3878 Flags |= MachineMemOperand::MOVolatile;
3880 MachineMemOperand *MMO =
3881 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3883 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3884 Ordering, SynchScope);
3887 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3889 SDValue Ptr, SDValue Cmp,
3890 SDValue Swp, MachineMemOperand *MMO,
3891 AtomicOrdering Ordering,
3892 SynchronizationScope SynchScope) {
3893 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3894 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3896 EVT VT = Cmp.getValueType();
3898 SDVTList VTs = getVTList(VT, MVT::Other);
3899 FoldingSetNodeID ID;
3900 ID.AddInteger(MemVT.getRawBits());
3901 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3902 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3904 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3905 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3906 return SDValue(E, 0);
3908 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3909 Ptr, Cmp, Swp, MMO, Ordering,
3911 CSEMap.InsertNode(N, IP);
3912 AllNodes.push_back(N);
3913 return SDValue(N, 0);
3916 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3918 SDValue Ptr, SDValue Val,
3919 const Value* PtrVal,
3921 AtomicOrdering Ordering,
3922 SynchronizationScope SynchScope) {
3923 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3924 Alignment = getEVTAlignment(MemVT);
3926 MachineFunction &MF = getMachineFunction();
3927 // A monotonic store does not load; a release store "loads" in the sense
3928 // that other stores cannot be sunk past it.
3929 // (An atomicrmw obviously both loads and stores.)
3930 unsigned Flags = MachineMemOperand::MOStore;
3931 if (Opcode != ISD::ATOMIC_STORE || Ordering > Monotonic)
3932 Flags |= MachineMemOperand::MOLoad;
3934 // For now, atomics are considered to be volatile always.
3935 // FIXME: Volatile isn't really correct; we should keep track of atomic
3936 // orderings in the memoperand.
3937 Flags |= MachineMemOperand::MOVolatile;
3939 MachineMemOperand *MMO =
3940 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
3941 MemVT.getStoreSize(), Alignment);
3943 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
3944 Ordering, SynchScope);
3947 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3949 SDValue Ptr, SDValue Val,
3950 MachineMemOperand *MMO,
3951 AtomicOrdering Ordering,
3952 SynchronizationScope SynchScope) {
3953 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
3954 Opcode == ISD::ATOMIC_LOAD_SUB ||
3955 Opcode == ISD::ATOMIC_LOAD_AND ||
3956 Opcode == ISD::ATOMIC_LOAD_OR ||
3957 Opcode == ISD::ATOMIC_LOAD_XOR ||
3958 Opcode == ISD::ATOMIC_LOAD_NAND ||
3959 Opcode == ISD::ATOMIC_LOAD_MIN ||
3960 Opcode == ISD::ATOMIC_LOAD_MAX ||
3961 Opcode == ISD::ATOMIC_LOAD_UMIN ||
3962 Opcode == ISD::ATOMIC_LOAD_UMAX ||
3963 Opcode == ISD::ATOMIC_SWAP ||
3964 Opcode == ISD::ATOMIC_STORE) &&
3965 "Invalid Atomic Op");
3967 EVT VT = Val.getValueType();
3969 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
3970 getVTList(VT, MVT::Other);
3971 FoldingSetNodeID ID;
3972 ID.AddInteger(MemVT.getRawBits());
3973 SDValue Ops[] = {Chain, Ptr, Val};
3974 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3976 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3977 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3978 return SDValue(E, 0);
3980 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3982 Ordering, SynchScope);
3983 CSEMap.InsertNode(N, IP);
3984 AllNodes.push_back(N);
3985 return SDValue(N, 0);
3988 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3989 EVT VT, SDValue Chain,
3991 const Value* PtrVal,
3993 AtomicOrdering Ordering,
3994 SynchronizationScope SynchScope) {
3995 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3996 Alignment = getEVTAlignment(MemVT);
3998 MachineFunction &MF = getMachineFunction();
3999 // A monotonic load does not store; an acquire load "stores" in the sense
4000 // that other loads cannot be hoisted past it.
4001 unsigned Flags = MachineMemOperand::MOLoad;
4002 if (Ordering > Monotonic)
4003 Flags |= MachineMemOperand::MOStore;
4005 // For now, atomics are considered to be volatile always.
4006 // FIXME: Volatile isn't really correct; we should keep track of atomic
4007 // orderings in the memoperand.
4008 Flags |= MachineMemOperand::MOVolatile;
4010 MachineMemOperand *MMO =
4011 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4012 MemVT.getStoreSize(), Alignment);
4014 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4015 Ordering, SynchScope);
4018 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4019 EVT VT, SDValue Chain,
4021 MachineMemOperand *MMO,
4022 AtomicOrdering Ordering,
4023 SynchronizationScope SynchScope) {
4024 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4026 SDVTList VTs = getVTList(VT, MVT::Other);
4027 FoldingSetNodeID ID;
4028 ID.AddInteger(MemVT.getRawBits());
4029 SDValue Ops[] = {Chain, Ptr};
4030 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4032 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4033 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4034 return SDValue(E, 0);
4036 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4037 Ptr, MMO, Ordering, SynchScope);
4038 CSEMap.InsertNode(N, IP);
4039 AllNodes.push_back(N);
4040 return SDValue(N, 0);
4043 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4044 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4049 SmallVector<EVT, 4> VTs;
4050 VTs.reserve(NumOps);
4051 for (unsigned i = 0; i < NumOps; ++i)
4052 VTs.push_back(Ops[i].getValueType());
4053 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4058 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4059 const EVT *VTs, unsigned NumVTs,
4060 const SDValue *Ops, unsigned NumOps,
4061 EVT MemVT, MachinePointerInfo PtrInfo,
4062 unsigned Align, bool Vol,
4063 bool ReadMem, bool WriteMem) {
4064 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4065 MemVT, PtrInfo, Align, Vol,
4070 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4071 const SDValue *Ops, unsigned NumOps,
4072 EVT MemVT, MachinePointerInfo PtrInfo,
4073 unsigned Align, bool Vol,
4074 bool ReadMem, bool WriteMem) {
4075 if (Align == 0) // Ensure that codegen never sees alignment 0
4076 Align = getEVTAlignment(MemVT);
4078 MachineFunction &MF = getMachineFunction();
4081 Flags |= MachineMemOperand::MOStore;
4083 Flags |= MachineMemOperand::MOLoad;
4085 Flags |= MachineMemOperand::MOVolatile;
4086 MachineMemOperand *MMO =
4087 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4089 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4093 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4094 const SDValue *Ops, unsigned NumOps,
4095 EVT MemVT, MachineMemOperand *MMO) {
4096 assert((Opcode == ISD::INTRINSIC_VOID ||
4097 Opcode == ISD::INTRINSIC_W_CHAIN ||
4098 Opcode == ISD::PREFETCH ||
4099 (Opcode <= INT_MAX &&
4100 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4101 "Opcode is not a memory-accessing opcode!");
4103 // Memoize the node unless it returns a flag.
4104 MemIntrinsicSDNode *N;
4105 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4106 FoldingSetNodeID ID;
4107 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4109 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4110 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4111 return SDValue(E, 0);
4114 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4116 CSEMap.InsertNode(N, IP);
4118 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4121 AllNodes.push_back(N);
4122 return SDValue(N, 0);
4125 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4126 /// MachinePointerInfo record from it. This is particularly useful because the
4127 /// code generator has many cases where it doesn't bother passing in a
4128 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4129 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4130 // If this is FI+Offset, we can model it.
4131 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4132 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4134 // If this is (FI+Offset1)+Offset2, we can model it.
4135 if (Ptr.getOpcode() != ISD::ADD ||
4136 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4137 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4138 return MachinePointerInfo();
4140 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4141 return MachinePointerInfo::getFixedStack(FI, Offset+
4142 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4145 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4146 /// MachinePointerInfo record from it. This is particularly useful because the
4147 /// code generator has many cases where it doesn't bother passing in a
4148 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4149 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4150 // If the 'Offset' value isn't a constant, we can't handle this.
4151 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4152 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4153 if (OffsetOp.getOpcode() == ISD::UNDEF)
4154 return InferPointerInfo(Ptr);
4155 return MachinePointerInfo();
4160 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4161 EVT VT, DebugLoc dl, SDValue Chain,
4162 SDValue Ptr, SDValue Offset,
4163 MachinePointerInfo PtrInfo, EVT MemVT,
4164 bool isVolatile, bool isNonTemporal, bool isInvariant,
4165 unsigned Alignment, const MDNode *TBAAInfo,
4166 const MDNode *Ranges) {
4167 assert(Chain.getValueType() == MVT::Other &&
4168 "Invalid chain type");
4169 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4170 Alignment = getEVTAlignment(VT);
4172 unsigned Flags = MachineMemOperand::MOLoad;
4174 Flags |= MachineMemOperand::MOVolatile;
4176 Flags |= MachineMemOperand::MONonTemporal;
4178 Flags |= MachineMemOperand::MOInvariant;
4180 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4183 PtrInfo = InferPointerInfo(Ptr, Offset);
4185 MachineFunction &MF = getMachineFunction();
4186 MachineMemOperand *MMO =
4187 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4189 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4193 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4194 EVT VT, DebugLoc dl, SDValue Chain,
4195 SDValue Ptr, SDValue Offset, EVT MemVT,
4196 MachineMemOperand *MMO) {
4198 ExtType = ISD::NON_EXTLOAD;
4199 } else if (ExtType == ISD::NON_EXTLOAD) {
4200 assert(VT == MemVT && "Non-extending load from different memory type!");
4203 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4204 "Should only be an extending load, not truncating!");
4205 assert(VT.isInteger() == MemVT.isInteger() &&
4206 "Cannot convert from FP to Int or Int -> FP!");
4207 assert(VT.isVector() == MemVT.isVector() &&
4208 "Cannot use trunc store to convert to or from a vector!");
4209 assert((!VT.isVector() ||
4210 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4211 "Cannot use trunc store to change the number of vector elements!");
4214 bool Indexed = AM != ISD::UNINDEXED;
4215 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4216 "Unindexed load with an offset!");
4218 SDVTList VTs = Indexed ?
4219 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4220 SDValue Ops[] = { Chain, Ptr, Offset };
4221 FoldingSetNodeID ID;
4222 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4223 ID.AddInteger(MemVT.getRawBits());
4224 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4225 MMO->isNonTemporal(),
4226 MMO->isInvariant()));
4228 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4229 cast<LoadSDNode>(E)->refineAlignment(MMO);
4230 return SDValue(E, 0);
4232 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4234 CSEMap.InsertNode(N, IP);
4235 AllNodes.push_back(N);
4236 return SDValue(N, 0);
4239 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4240 SDValue Chain, SDValue Ptr,
4241 MachinePointerInfo PtrInfo,
4242 bool isVolatile, bool isNonTemporal,
4243 bool isInvariant, unsigned Alignment,
4244 const MDNode *TBAAInfo,
4245 const MDNode *Ranges) {
4246 SDValue Undef = getUNDEF(Ptr.getValueType());
4247 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4248 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4252 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4253 SDValue Chain, SDValue Ptr,
4254 MachinePointerInfo PtrInfo, EVT MemVT,
4255 bool isVolatile, bool isNonTemporal,
4256 unsigned Alignment, const MDNode *TBAAInfo) {
4257 SDValue Undef = getUNDEF(Ptr.getValueType());
4258 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4259 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4265 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4266 SDValue Offset, ISD::MemIndexedMode AM) {
4267 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4268 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4269 "Load is already a indexed load!");
4270 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4271 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4272 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4273 false, LD->getAlignment());
4276 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4277 SDValue Ptr, MachinePointerInfo PtrInfo,
4278 bool isVolatile, bool isNonTemporal,
4279 unsigned Alignment, const MDNode *TBAAInfo) {
4280 assert(Chain.getValueType() == MVT::Other &&
4281 "Invalid chain type");
4282 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4283 Alignment = getEVTAlignment(Val.getValueType());
4285 unsigned Flags = MachineMemOperand::MOStore;
4287 Flags |= MachineMemOperand::MOVolatile;
4289 Flags |= MachineMemOperand::MONonTemporal;
4292 PtrInfo = InferPointerInfo(Ptr);
4294 MachineFunction &MF = getMachineFunction();
4295 MachineMemOperand *MMO =
4296 MF.getMachineMemOperand(PtrInfo, Flags,
4297 Val.getValueType().getStoreSize(), Alignment,
4300 return getStore(Chain, dl, Val, Ptr, MMO);
4303 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4304 SDValue Ptr, MachineMemOperand *MMO) {
4305 assert(Chain.getValueType() == MVT::Other &&
4306 "Invalid chain type");
4307 EVT VT = Val.getValueType();
4308 SDVTList VTs = getVTList(MVT::Other);
4309 SDValue Undef = getUNDEF(Ptr.getValueType());
4310 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4311 FoldingSetNodeID ID;
4312 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4313 ID.AddInteger(VT.getRawBits());
4314 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4315 MMO->isNonTemporal(), MMO->isInvariant()));
4317 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4318 cast<StoreSDNode>(E)->refineAlignment(MMO);
4319 return SDValue(E, 0);
4321 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4323 CSEMap.InsertNode(N, IP);
4324 AllNodes.push_back(N);
4325 return SDValue(N, 0);
4328 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4329 SDValue Ptr, MachinePointerInfo PtrInfo,
4330 EVT SVT,bool isVolatile, bool isNonTemporal,
4332 const MDNode *TBAAInfo) {
4333 assert(Chain.getValueType() == MVT::Other &&
4334 "Invalid chain type");
4335 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4336 Alignment = getEVTAlignment(SVT);
4338 unsigned Flags = MachineMemOperand::MOStore;
4340 Flags |= MachineMemOperand::MOVolatile;
4342 Flags |= MachineMemOperand::MONonTemporal;
4345 PtrInfo = InferPointerInfo(Ptr);
4347 MachineFunction &MF = getMachineFunction();
4348 MachineMemOperand *MMO =
4349 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4352 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4355 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4356 SDValue Ptr, EVT SVT,
4357 MachineMemOperand *MMO) {
4358 EVT VT = Val.getValueType();
4360 assert(Chain.getValueType() == MVT::Other &&
4361 "Invalid chain type");
4363 return getStore(Chain, dl, Val, Ptr, MMO);
4365 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4366 "Should only be a truncating store, not extending!");
4367 assert(VT.isInteger() == SVT.isInteger() &&
4368 "Can't do FP-INT conversion!");
4369 assert(VT.isVector() == SVT.isVector() &&
4370 "Cannot use trunc store to convert to or from a vector!");
4371 assert((!VT.isVector() ||
4372 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4373 "Cannot use trunc store to change the number of vector elements!");
4375 SDVTList VTs = getVTList(MVT::Other);
4376 SDValue Undef = getUNDEF(Ptr.getValueType());
4377 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4378 FoldingSetNodeID ID;
4379 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4380 ID.AddInteger(SVT.getRawBits());
4381 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4382 MMO->isNonTemporal(), MMO->isInvariant()));
4384 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4385 cast<StoreSDNode>(E)->refineAlignment(MMO);
4386 return SDValue(E, 0);
4388 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4390 CSEMap.InsertNode(N, IP);
4391 AllNodes.push_back(N);
4392 return SDValue(N, 0);
4396 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4397 SDValue Offset, ISD::MemIndexedMode AM) {
4398 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4399 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4400 "Store is already a indexed store!");
4401 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4402 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4403 FoldingSetNodeID ID;
4404 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4405 ID.AddInteger(ST->getMemoryVT().getRawBits());
4406 ID.AddInteger(ST->getRawSubclassData());
4408 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4409 return SDValue(E, 0);
4411 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4412 ST->isTruncatingStore(),
4414 ST->getMemOperand());
4415 CSEMap.InsertNode(N, IP);
4416 AllNodes.push_back(N);
4417 return SDValue(N, 0);
4420 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4421 SDValue Chain, SDValue Ptr,
4424 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4425 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4428 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4429 const SDUse *Ops, unsigned NumOps) {
4431 case 0: return getNode(Opcode, DL, VT);
4432 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4433 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4434 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4438 // Copy from an SDUse array into an SDValue array for use with
4439 // the regular getNode logic.
4440 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4441 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4444 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4445 const SDValue *Ops, unsigned NumOps) {
4447 case 0: return getNode(Opcode, DL, VT);
4448 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4449 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4450 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4456 case ISD::SELECT_CC: {
4457 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4458 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4459 "LHS and RHS of condition must have same type!");
4460 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4461 "True and False arms of SelectCC must have same type!");
4462 assert(Ops[2].getValueType() == VT &&
4463 "select_cc node must be of same type as true and false value!");
4467 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4468 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4469 "LHS/RHS of comparison should match types!");
4476 SDVTList VTs = getVTList(VT);
4478 if (VT != MVT::Glue) {
4479 FoldingSetNodeID ID;
4480 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4483 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4484 return SDValue(E, 0);
4486 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4487 CSEMap.InsertNode(N, IP);
4489 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4492 AllNodes.push_back(N);
4496 return SDValue(N, 0);
4499 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4500 const std::vector<EVT> &ResultTys,
4501 const SDValue *Ops, unsigned NumOps) {
4502 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4506 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4507 const EVT *VTs, unsigned NumVTs,
4508 const SDValue *Ops, unsigned NumOps) {
4510 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4511 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4514 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4515 const SDValue *Ops, unsigned NumOps) {
4516 if (VTList.NumVTs == 1)
4517 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4521 // FIXME: figure out how to safely handle things like
4522 // int foo(int x) { return 1 << (x & 255); }
4523 // int bar() { return foo(256); }
4524 case ISD::SRA_PARTS:
4525 case ISD::SRL_PARTS:
4526 case ISD::SHL_PARTS:
4527 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4528 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4529 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4530 else if (N3.getOpcode() == ISD::AND)
4531 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4532 // If the and is only masking out bits that cannot effect the shift,
4533 // eliminate the and.
4534 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4535 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4536 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4542 // Memoize the node unless it returns a flag.
4544 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4545 FoldingSetNodeID ID;
4546 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4548 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4549 return SDValue(E, 0);
4552 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4553 } else if (NumOps == 2) {
4554 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4555 } else if (NumOps == 3) {
4556 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4559 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4561 CSEMap.InsertNode(N, IP);
4564 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4565 } else if (NumOps == 2) {
4566 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4567 } else if (NumOps == 3) {
4568 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4571 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4574 AllNodes.push_back(N);
4578 return SDValue(N, 0);
4581 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4582 return getNode(Opcode, DL, VTList, 0, 0);
4585 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4587 SDValue Ops[] = { N1 };
4588 return getNode(Opcode, DL, VTList, Ops, 1);
4591 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4592 SDValue N1, SDValue N2) {
4593 SDValue Ops[] = { N1, N2 };
4594 return getNode(Opcode, DL, VTList, Ops, 2);
4597 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4598 SDValue N1, SDValue N2, SDValue N3) {
4599 SDValue Ops[] = { N1, N2, N3 };
4600 return getNode(Opcode, DL, VTList, Ops, 3);
4603 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4604 SDValue N1, SDValue N2, SDValue N3,
4606 SDValue Ops[] = { N1, N2, N3, N4 };
4607 return getNode(Opcode, DL, VTList, Ops, 4);
4610 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4611 SDValue N1, SDValue N2, SDValue N3,
4612 SDValue N4, SDValue N5) {
4613 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4614 return getNode(Opcode, DL, VTList, Ops, 5);
4617 SDVTList SelectionDAG::getVTList(EVT VT) {
4618 return makeVTList(SDNode::getValueTypeList(VT), 1);
4621 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4622 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4623 E = VTList.rend(); I != E; ++I)
4624 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4627 EVT *Array = Allocator.Allocate<EVT>(2);
4630 SDVTList Result = makeVTList(Array, 2);
4631 VTList.push_back(Result);
4635 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4636 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4637 E = VTList.rend(); I != E; ++I)
4638 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4642 EVT *Array = Allocator.Allocate<EVT>(3);
4646 SDVTList Result = makeVTList(Array, 3);
4647 VTList.push_back(Result);
4651 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4652 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4653 E = VTList.rend(); I != E; ++I)
4654 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4655 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4658 EVT *Array = Allocator.Allocate<EVT>(4);
4663 SDVTList Result = makeVTList(Array, 4);
4664 VTList.push_back(Result);
4668 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4670 case 0: llvm_unreachable("Cannot have nodes without results!");
4671 case 1: return getVTList(VTs[0]);
4672 case 2: return getVTList(VTs[0], VTs[1]);
4673 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4674 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4678 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4679 E = VTList.rend(); I != E; ++I) {
4680 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4683 bool NoMatch = false;
4684 for (unsigned i = 2; i != NumVTs; ++i)
4685 if (VTs[i] != I->VTs[i]) {
4693 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4694 std::copy(VTs, VTs+NumVTs, Array);
4695 SDVTList Result = makeVTList(Array, NumVTs);
4696 VTList.push_back(Result);
4701 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4702 /// specified operands. If the resultant node already exists in the DAG,
4703 /// this does not modify the specified node, instead it returns the node that
4704 /// already exists. If the resultant node does not exist in the DAG, the
4705 /// input node is returned. As a degenerate case, if you specify the same
4706 /// input operands as the node already has, the input node is returned.
4707 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4708 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4710 // Check to see if there is no change.
4711 if (Op == N->getOperand(0)) return N;
4713 // See if the modified node already exists.
4714 void *InsertPos = 0;
4715 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4718 // Nope it doesn't. Remove the node from its current place in the maps.
4720 if (!RemoveNodeFromCSEMaps(N))
4723 // Now we update the operands.
4724 N->OperandList[0].set(Op);
4726 // If this gets put into a CSE map, add it.
4727 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4731 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4732 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4734 // Check to see if there is no change.
4735 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4736 return N; // No operands changed, just return the input node.
4738 // See if the modified node already exists.
4739 void *InsertPos = 0;
4740 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4743 // Nope it doesn't. Remove the node from its current place in the maps.
4745 if (!RemoveNodeFromCSEMaps(N))
4748 // Now we update the operands.
4749 if (N->OperandList[0] != Op1)
4750 N->OperandList[0].set(Op1);
4751 if (N->OperandList[1] != Op2)
4752 N->OperandList[1].set(Op2);
4754 // If this gets put into a CSE map, add it.
4755 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4759 SDNode *SelectionDAG::
4760 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4761 SDValue Ops[] = { Op1, Op2, Op3 };
4762 return UpdateNodeOperands(N, Ops, 3);
4765 SDNode *SelectionDAG::
4766 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4767 SDValue Op3, SDValue Op4) {
4768 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4769 return UpdateNodeOperands(N, Ops, 4);
4772 SDNode *SelectionDAG::
4773 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4774 SDValue Op3, SDValue Op4, SDValue Op5) {
4775 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4776 return UpdateNodeOperands(N, Ops, 5);
4779 SDNode *SelectionDAG::
4780 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4781 assert(N->getNumOperands() == NumOps &&
4782 "Update with wrong number of operands");
4784 // Check to see if there is no change.
4785 bool AnyChange = false;
4786 for (unsigned i = 0; i != NumOps; ++i) {
4787 if (Ops[i] != N->getOperand(i)) {
4793 // No operands changed, just return the input node.
4794 if (!AnyChange) return N;
4796 // See if the modified node already exists.
4797 void *InsertPos = 0;
4798 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4801 // Nope it doesn't. Remove the node from its current place in the maps.
4803 if (!RemoveNodeFromCSEMaps(N))
4806 // Now we update the operands.
4807 for (unsigned i = 0; i != NumOps; ++i)
4808 if (N->OperandList[i] != Ops[i])
4809 N->OperandList[i].set(Ops[i]);
4811 // If this gets put into a CSE map, add it.
4812 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4816 /// DropOperands - Release the operands and set this node to have
4818 void SDNode::DropOperands() {
4819 // Unlike the code in MorphNodeTo that does this, we don't need to
4820 // watch for dead nodes here.
4821 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4827 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4830 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4832 SDVTList VTs = getVTList(VT);
4833 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4836 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4837 EVT VT, SDValue Op1) {
4838 SDVTList VTs = getVTList(VT);
4839 SDValue Ops[] = { Op1 };
4840 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4843 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4844 EVT VT, SDValue Op1,
4846 SDVTList VTs = getVTList(VT);
4847 SDValue Ops[] = { Op1, Op2 };
4848 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4851 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4852 EVT VT, SDValue Op1,
4853 SDValue Op2, SDValue Op3) {
4854 SDVTList VTs = getVTList(VT);
4855 SDValue Ops[] = { Op1, Op2, Op3 };
4856 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4859 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4860 EVT VT, const SDValue *Ops,
4862 SDVTList VTs = getVTList(VT);
4863 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4866 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4867 EVT VT1, EVT VT2, const SDValue *Ops,
4869 SDVTList VTs = getVTList(VT1, VT2);
4870 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4873 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4875 SDVTList VTs = getVTList(VT1, VT2);
4876 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4879 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4880 EVT VT1, EVT VT2, EVT VT3,
4881 const SDValue *Ops, unsigned NumOps) {
4882 SDVTList VTs = getVTList(VT1, VT2, VT3);
4883 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4886 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4887 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4888 const SDValue *Ops, unsigned NumOps) {
4889 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4890 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4893 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4896 SDVTList VTs = getVTList(VT1, VT2);
4897 SDValue Ops[] = { Op1 };
4898 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4901 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4903 SDValue Op1, SDValue Op2) {
4904 SDVTList VTs = getVTList(VT1, VT2);
4905 SDValue Ops[] = { Op1, Op2 };
4906 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4909 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4911 SDValue Op1, SDValue Op2,
4913 SDVTList VTs = getVTList(VT1, VT2);
4914 SDValue Ops[] = { Op1, Op2, Op3 };
4915 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4918 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4919 EVT VT1, EVT VT2, EVT VT3,
4920 SDValue Op1, SDValue Op2,
4922 SDVTList VTs = getVTList(VT1, VT2, VT3);
4923 SDValue Ops[] = { Op1, Op2, Op3 };
4924 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4927 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4928 SDVTList VTs, const SDValue *Ops,
4930 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
4931 // Reset the NodeID to -1.
4936 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
4937 /// the line number information on the merged node since it is not possible to
4938 /// preserve the information that operation is associated with multiple lines.
4939 /// This will make the debugger working better at -O0, were there is a higher
4940 /// probability having other instructions associated with that line.
4942 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
4943 DebugLoc NLoc = N->getDebugLoc();
4944 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
4945 N->setDebugLoc(DebugLoc());
4950 /// MorphNodeTo - This *mutates* the specified node to have the specified
4951 /// return type, opcode, and operands.
4953 /// Note that MorphNodeTo returns the resultant node. If there is already a
4954 /// node of the specified opcode and operands, it returns that node instead of
4955 /// the current one. Note that the DebugLoc need not be the same.
4957 /// Using MorphNodeTo is faster than creating a new node and swapping it in
4958 /// with ReplaceAllUsesWith both because it often avoids allocating a new
4959 /// node, and because it doesn't require CSE recalculation for any of
4960 /// the node's users.
4962 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
4963 SDVTList VTs, const SDValue *Ops,
4965 // If an identical node already exists, use it.
4967 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
4968 FoldingSetNodeID ID;
4969 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
4970 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
4971 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
4974 if (!RemoveNodeFromCSEMaps(N))
4977 // Start the morphing.
4979 N->ValueList = VTs.VTs;
4980 N->NumValues = VTs.NumVTs;
4982 // Clear the operands list, updating used nodes to remove this from their
4983 // use list. Keep track of any operands that become dead as a result.
4984 SmallPtrSet<SDNode*, 16> DeadNodeSet;
4985 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
4987 SDNode *Used = Use.getNode();
4989 if (Used->use_empty())
4990 DeadNodeSet.insert(Used);
4993 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
4994 // Initialize the memory references information.
4995 MN->setMemRefs(0, 0);
4996 // If NumOps is larger than the # of operands we can have in a
4997 // MachineSDNode, reallocate the operand list.
4998 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
4999 if (MN->OperandsNeedDelete)
5000 delete[] MN->OperandList;
5001 if (NumOps > array_lengthof(MN->LocalOperands))
5002 // We're creating a final node that will live unmorphed for the
5003 // remainder of the current SelectionDAG iteration, so we can allocate
5004 // the operands directly out of a pool with no recycling metadata.
5005 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5008 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5009 MN->OperandsNeedDelete = false;
5011 MN->InitOperands(MN->OperandList, Ops, NumOps);
5013 // If NumOps is larger than the # of operands we currently have, reallocate
5014 // the operand list.
5015 if (NumOps > N->NumOperands) {
5016 if (N->OperandsNeedDelete)
5017 delete[] N->OperandList;
5018 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5019 N->OperandsNeedDelete = true;
5021 N->InitOperands(N->OperandList, Ops, NumOps);
5024 // Delete any nodes that are still dead after adding the uses for the
5026 if (!DeadNodeSet.empty()) {
5027 SmallVector<SDNode *, 16> DeadNodes;
5028 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5029 E = DeadNodeSet.end(); I != E; ++I)
5030 if ((*I)->use_empty())
5031 DeadNodes.push_back(*I);
5032 RemoveDeadNodes(DeadNodes);
5036 CSEMap.InsertNode(N, IP); // Memoize the new node.
5041 /// getMachineNode - These are used for target selectors to create a new node
5042 /// with specified return type(s), MachineInstr opcode, and operands.
5044 /// Note that getMachineNode returns the resultant node. If there is already a
5045 /// node of the specified opcode and operands, it returns that node instead of
5046 /// the current one.
5048 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5049 SDVTList VTs = getVTList(VT);
5050 return getMachineNode(Opcode, dl, VTs, 0, 0);
5054 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5055 SDVTList VTs = getVTList(VT);
5056 SDValue Ops[] = { Op1 };
5057 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5061 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5062 SDValue Op1, SDValue Op2) {
5063 SDVTList VTs = getVTList(VT);
5064 SDValue Ops[] = { Op1, Op2 };
5065 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5069 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5070 SDValue Op1, SDValue Op2, SDValue Op3) {
5071 SDVTList VTs = getVTList(VT);
5072 SDValue Ops[] = { Op1, Op2, Op3 };
5073 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5077 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5078 const SDValue *Ops, unsigned NumOps) {
5079 SDVTList VTs = getVTList(VT);
5080 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5084 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5085 SDVTList VTs = getVTList(VT1, VT2);
5086 return getMachineNode(Opcode, dl, VTs, 0, 0);
5090 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5091 EVT VT1, EVT VT2, SDValue Op1) {
5092 SDVTList VTs = getVTList(VT1, VT2);
5093 SDValue Ops[] = { Op1 };
5094 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5098 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5099 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5100 SDVTList VTs = getVTList(VT1, VT2);
5101 SDValue Ops[] = { Op1, Op2 };
5102 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5106 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5107 EVT VT1, EVT VT2, SDValue Op1,
5108 SDValue Op2, SDValue Op3) {
5109 SDVTList VTs = getVTList(VT1, VT2);
5110 SDValue Ops[] = { Op1, Op2, Op3 };
5111 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5115 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5117 const SDValue *Ops, unsigned NumOps) {
5118 SDVTList VTs = getVTList(VT1, VT2);
5119 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5123 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5124 EVT VT1, EVT VT2, EVT VT3,
5125 SDValue Op1, SDValue Op2) {
5126 SDVTList VTs = getVTList(VT1, VT2, VT3);
5127 SDValue Ops[] = { Op1, Op2 };
5128 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5132 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5133 EVT VT1, EVT VT2, EVT VT3,
5134 SDValue Op1, SDValue Op2, SDValue Op3) {
5135 SDVTList VTs = getVTList(VT1, VT2, VT3);
5136 SDValue Ops[] = { Op1, Op2, Op3 };
5137 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5141 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5142 EVT VT1, EVT VT2, EVT VT3,
5143 const SDValue *Ops, unsigned NumOps) {
5144 SDVTList VTs = getVTList(VT1, VT2, VT3);
5145 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5149 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5150 EVT VT2, EVT VT3, EVT VT4,
5151 const SDValue *Ops, unsigned NumOps) {
5152 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5153 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5157 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5158 const std::vector<EVT> &ResultTys,
5159 const SDValue *Ops, unsigned NumOps) {
5160 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5161 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5165 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5166 const SDValue *Ops, unsigned NumOps) {
5167 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5172 FoldingSetNodeID ID;
5173 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5175 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5176 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5180 // Allocate a new MachineSDNode.
5181 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5183 // Initialize the operands list.
5184 if (NumOps > array_lengthof(N->LocalOperands))
5185 // We're creating a final node that will live unmorphed for the
5186 // remainder of the current SelectionDAG iteration, so we can allocate
5187 // the operands directly out of a pool with no recycling metadata.
5188 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5191 N->InitOperands(N->LocalOperands, Ops, NumOps);
5192 N->OperandsNeedDelete = false;
5195 CSEMap.InsertNode(N, IP);
5197 AllNodes.push_back(N);
5199 VerifyMachineNode(N);
5204 /// getTargetExtractSubreg - A convenience function for creating
5205 /// TargetOpcode::EXTRACT_SUBREG nodes.
5207 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5209 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5210 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5211 VT, Operand, SRIdxVal);
5212 return SDValue(Subreg, 0);
5215 /// getTargetInsertSubreg - A convenience function for creating
5216 /// TargetOpcode::INSERT_SUBREG nodes.
5218 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5219 SDValue Operand, SDValue Subreg) {
5220 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5221 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5222 VT, Operand, Subreg, SRIdxVal);
5223 return SDValue(Result, 0);
5226 /// getNodeIfExists - Get the specified node if it's already available, or
5227 /// else return NULL.
5228 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5229 const SDValue *Ops, unsigned NumOps) {
5230 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5231 FoldingSetNodeID ID;
5232 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5234 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5240 /// getDbgValue - Creates a SDDbgValue node.
5243 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5244 DebugLoc DL, unsigned O) {
5245 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5249 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5250 DebugLoc DL, unsigned O) {
5251 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5255 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5256 DebugLoc DL, unsigned O) {
5257 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5262 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5263 /// pointed to by a use iterator is deleted, increment the use iterator
5264 /// so that it doesn't dangle.
5266 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5267 SDNode::use_iterator &UI;
5268 SDNode::use_iterator &UE;
5270 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5271 // Increment the iterator as needed.
5272 while (UI != UE && N == *UI)
5277 RAUWUpdateListener(SelectionDAG &d,
5278 SDNode::use_iterator &ui,
5279 SDNode::use_iterator &ue)
5280 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5285 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5286 /// This can cause recursive merging of nodes in the DAG.
5288 /// This version assumes From has a single result value.
5290 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5291 SDNode *From = FromN.getNode();
5292 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5293 "Cannot replace with this method!");
5294 assert(From != To.getNode() && "Cannot replace uses of with self");
5296 // Iterate over all the existing uses of From. New uses will be added
5297 // to the beginning of the use list, which we avoid visiting.
5298 // This specifically avoids visiting uses of From that arise while the
5299 // replacement is happening, because any such uses would be the result
5300 // of CSE: If an existing node looks like From after one of its operands
5301 // is replaced by To, we don't want to replace of all its users with To
5302 // too. See PR3018 for more info.
5303 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5304 RAUWUpdateListener Listener(*this, UI, UE);
5308 // This node is about to morph, remove its old self from the CSE maps.
5309 RemoveNodeFromCSEMaps(User);
5311 // A user can appear in a use list multiple times, and when this
5312 // happens the uses are usually next to each other in the list.
5313 // To help reduce the number of CSE recomputations, process all
5314 // the uses of this user that we can find this way.
5316 SDUse &Use = UI.getUse();
5319 } while (UI != UE && *UI == User);
5321 // Now that we have modified User, add it back to the CSE maps. If it
5322 // already exists there, recursively merge the results together.
5323 AddModifiedNodeToCSEMaps(User);
5326 // If we just RAUW'd the root, take note.
5327 if (FromN == getRoot())
5331 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5332 /// This can cause recursive merging of nodes in the DAG.
5334 /// This version assumes that for each value of From, there is a
5335 /// corresponding value in To in the same position with the same type.
5337 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5339 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5340 assert((!From->hasAnyUseOfValue(i) ||
5341 From->getValueType(i) == To->getValueType(i)) &&
5342 "Cannot use this version of ReplaceAllUsesWith!");
5345 // Handle the trivial case.
5349 // Iterate over just the existing users of From. See the comments in
5350 // the ReplaceAllUsesWith above.
5351 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5352 RAUWUpdateListener Listener(*this, UI, UE);
5356 // This node is about to morph, remove its old self from the CSE maps.
5357 RemoveNodeFromCSEMaps(User);
5359 // A user can appear in a use list multiple times, and when this
5360 // happens the uses are usually next to each other in the list.
5361 // To help reduce the number of CSE recomputations, process all
5362 // the uses of this user that we can find this way.
5364 SDUse &Use = UI.getUse();
5367 } while (UI != UE && *UI == User);
5369 // Now that we have modified User, add it back to the CSE maps. If it
5370 // already exists there, recursively merge the results together.
5371 AddModifiedNodeToCSEMaps(User);
5374 // If we just RAUW'd the root, take note.
5375 if (From == getRoot().getNode())
5376 setRoot(SDValue(To, getRoot().getResNo()));
5379 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5380 /// This can cause recursive merging of nodes in the DAG.
5382 /// This version can replace From with any result values. To must match the
5383 /// number and types of values returned by From.
5384 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5385 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5386 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5388 // Iterate over just the existing users of From. See the comments in
5389 // the ReplaceAllUsesWith above.
5390 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5391 RAUWUpdateListener Listener(*this, UI, UE);
5395 // This node is about to morph, remove its old self from the CSE maps.
5396 RemoveNodeFromCSEMaps(User);
5398 // A user can appear in a use list multiple times, and when this
5399 // happens the uses are usually next to each other in the list.
5400 // To help reduce the number of CSE recomputations, process all
5401 // the uses of this user that we can find this way.
5403 SDUse &Use = UI.getUse();
5404 const SDValue &ToOp = To[Use.getResNo()];
5407 } while (UI != UE && *UI == User);
5409 // Now that we have modified User, add it back to the CSE maps. If it
5410 // already exists there, recursively merge the results together.
5411 AddModifiedNodeToCSEMaps(User);
5414 // If we just RAUW'd the root, take note.
5415 if (From == getRoot().getNode())
5416 setRoot(SDValue(To[getRoot().getResNo()]));
5419 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5420 /// uses of other values produced by From.getNode() alone. The Deleted
5421 /// vector is handled the same way as for ReplaceAllUsesWith.
5422 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5423 // Handle the really simple, really trivial case efficiently.
5424 if (From == To) return;
5426 // Handle the simple, trivial, case efficiently.
5427 if (From.getNode()->getNumValues() == 1) {
5428 ReplaceAllUsesWith(From, To);
5432 // Iterate over just the existing users of From. See the comments in
5433 // the ReplaceAllUsesWith above.
5434 SDNode::use_iterator UI = From.getNode()->use_begin(),
5435 UE = From.getNode()->use_end();
5436 RAUWUpdateListener Listener(*this, UI, UE);
5439 bool UserRemovedFromCSEMaps = false;
5441 // A user can appear in a use list multiple times, and when this
5442 // happens the uses are usually next to each other in the list.
5443 // To help reduce the number of CSE recomputations, process all
5444 // the uses of this user that we can find this way.
5446 SDUse &Use = UI.getUse();
5448 // Skip uses of different values from the same node.
5449 if (Use.getResNo() != From.getResNo()) {
5454 // If this node hasn't been modified yet, it's still in the CSE maps,
5455 // so remove its old self from the CSE maps.
5456 if (!UserRemovedFromCSEMaps) {
5457 RemoveNodeFromCSEMaps(User);
5458 UserRemovedFromCSEMaps = true;
5463 } while (UI != UE && *UI == User);
5465 // We are iterating over all uses of the From node, so if a use
5466 // doesn't use the specific value, no changes are made.
5467 if (!UserRemovedFromCSEMaps)
5470 // Now that we have modified User, add it back to the CSE maps. If it
5471 // already exists there, recursively merge the results together.
5472 AddModifiedNodeToCSEMaps(User);
5475 // If we just RAUW'd the root, take note.
5476 if (From == getRoot())
5481 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5482 /// to record information about a use.
5489 /// operator< - Sort Memos by User.
5490 bool operator<(const UseMemo &L, const UseMemo &R) {
5491 return (intptr_t)L.User < (intptr_t)R.User;
5495 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5496 /// uses of other values produced by From.getNode() alone. The same value
5497 /// may appear in both the From and To list. The Deleted vector is
5498 /// handled the same way as for ReplaceAllUsesWith.
5499 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5502 // Handle the simple, trivial case efficiently.
5504 return ReplaceAllUsesOfValueWith(*From, *To);
5506 // Read up all the uses and make records of them. This helps
5507 // processing new uses that are introduced during the
5508 // replacement process.
5509 SmallVector<UseMemo, 4> Uses;
5510 for (unsigned i = 0; i != Num; ++i) {
5511 unsigned FromResNo = From[i].getResNo();
5512 SDNode *FromNode = From[i].getNode();
5513 for (SDNode::use_iterator UI = FromNode->use_begin(),
5514 E = FromNode->use_end(); UI != E; ++UI) {
5515 SDUse &Use = UI.getUse();
5516 if (Use.getResNo() == FromResNo) {
5517 UseMemo Memo = { *UI, i, &Use };
5518 Uses.push_back(Memo);
5523 // Sort the uses, so that all the uses from a given User are together.
5524 std::sort(Uses.begin(), Uses.end());
5526 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5527 UseIndex != UseIndexEnd; ) {
5528 // We know that this user uses some value of From. If it is the right
5529 // value, update it.
5530 SDNode *User = Uses[UseIndex].User;
5532 // This node is about to morph, remove its old self from the CSE maps.
5533 RemoveNodeFromCSEMaps(User);
5535 // The Uses array is sorted, so all the uses for a given User
5536 // are next to each other in the list.
5537 // To help reduce the number of CSE recomputations, process all
5538 // the uses of this user that we can find this way.
5540 unsigned i = Uses[UseIndex].Index;
5541 SDUse &Use = *Uses[UseIndex].Use;
5545 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5547 // Now that we have modified User, add it back to the CSE maps. If it
5548 // already exists there, recursively merge the results together.
5549 AddModifiedNodeToCSEMaps(User);
5553 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5554 /// based on their topological order. It returns the maximum id and a vector
5555 /// of the SDNodes* in assigned order by reference.
5556 unsigned SelectionDAG::AssignTopologicalOrder() {
5558 unsigned DAGSize = 0;
5560 // SortedPos tracks the progress of the algorithm. Nodes before it are
5561 // sorted, nodes after it are unsorted. When the algorithm completes
5562 // it is at the end of the list.
5563 allnodes_iterator SortedPos = allnodes_begin();
5565 // Visit all the nodes. Move nodes with no operands to the front of
5566 // the list immediately. Annotate nodes that do have operands with their
5567 // operand count. Before we do this, the Node Id fields of the nodes
5568 // may contain arbitrary values. After, the Node Id fields for nodes
5569 // before SortedPos will contain the topological sort index, and the
5570 // Node Id fields for nodes At SortedPos and after will contain the
5571 // count of outstanding operands.
5572 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5575 unsigned Degree = N->getNumOperands();
5577 // A node with no uses, add it to the result array immediately.
5578 N->setNodeId(DAGSize++);
5579 allnodes_iterator Q = N;
5581 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5582 assert(SortedPos != AllNodes.end() && "Overran node list");
5585 // Temporarily use the Node Id as scratch space for the degree count.
5586 N->setNodeId(Degree);
5590 // Visit all the nodes. As we iterate, move nodes into sorted order,
5591 // such that by the time the end is reached all nodes will be sorted.
5592 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5595 // N is in sorted position, so all its uses have one less operand
5596 // that needs to be sorted.
5597 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5600 unsigned Degree = P->getNodeId();
5601 assert(Degree != 0 && "Invalid node degree");
5604 // All of P's operands are sorted, so P may sorted now.
5605 P->setNodeId(DAGSize++);
5607 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5608 assert(SortedPos != AllNodes.end() && "Overran node list");
5611 // Update P's outstanding operand count.
5612 P->setNodeId(Degree);
5615 if (I == SortedPos) {
5618 dbgs() << "Overran sorted position:\n";
5621 llvm_unreachable(0);
5625 assert(SortedPos == AllNodes.end() &&
5626 "Topological sort incomplete!");
5627 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5628 "First node in topological sort is not the entry token!");
5629 assert(AllNodes.front().getNodeId() == 0 &&
5630 "First node in topological sort has non-zero id!");
5631 assert(AllNodes.front().getNumOperands() == 0 &&
5632 "First node in topological sort has operands!");
5633 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5634 "Last node in topologic sort has unexpected id!");
5635 assert(AllNodes.back().use_empty() &&
5636 "Last node in topologic sort has users!");
5637 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5641 /// AssignOrdering - Assign an order to the SDNode.
5642 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5643 assert(SD && "Trying to assign an order to a null node!");
5644 Ordering->add(SD, Order);
5647 /// GetOrdering - Get the order for the SDNode.
5648 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5649 assert(SD && "Trying to get the order of a null node!");
5650 return Ordering->getOrder(SD);
5653 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5654 /// value is produced by SD.
5655 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5656 DbgInfo->add(DB, SD, isParameter);
5658 SD->setHasDebugValue(true);
5661 /// TransferDbgValues - Transfer SDDbgValues.
5662 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5663 if (From == To || !From.getNode()->getHasDebugValue())
5665 SDNode *FromNode = From.getNode();
5666 SDNode *ToNode = To.getNode();
5667 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5668 SmallVector<SDDbgValue *, 2> ClonedDVs;
5669 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5671 SDDbgValue *Dbg = *I;
5672 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5673 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5674 Dbg->getOffset(), Dbg->getDebugLoc(),
5676 ClonedDVs.push_back(Clone);
5679 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5680 E = ClonedDVs.end(); I != E; ++I)
5681 AddDbgValue(*I, ToNode, false);
5684 //===----------------------------------------------------------------------===//
5686 //===----------------------------------------------------------------------===//
5688 HandleSDNode::~HandleSDNode() {
5692 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5693 const GlobalValue *GA,
5694 EVT VT, int64_t o, unsigned char TF)
5695 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5699 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5700 MachineMemOperand *mmo)
5701 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5702 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5703 MMO->isNonTemporal(), MMO->isInvariant());
5704 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5705 assert(isNonTemporal() == MMO->isNonTemporal() &&
5706 "Non-temporal encoding error!");
5707 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5710 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5711 const SDValue *Ops, unsigned NumOps, EVT memvt,
5712 MachineMemOperand *mmo)
5713 : SDNode(Opc, dl, VTs, Ops, NumOps),
5714 MemoryVT(memvt), MMO(mmo) {
5715 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5716 MMO->isNonTemporal(), MMO->isInvariant());
5717 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5718 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5721 /// Profile - Gather unique data for the node.
5723 void SDNode::Profile(FoldingSetNodeID &ID) const {
5724 AddNodeIDNode(ID, this);
5729 std::vector<EVT> VTs;
5732 VTs.reserve(MVT::LAST_VALUETYPE);
5733 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5734 VTs.push_back(MVT((MVT::SimpleValueType)i));
5739 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5740 static ManagedStatic<EVTArray> SimpleVTArray;
5741 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5743 /// getValueTypeList - Return a pointer to the specified value type.
5745 const EVT *SDNode::getValueTypeList(EVT VT) {
5746 if (VT.isExtended()) {
5747 sys::SmartScopedLock<true> Lock(*VTMutex);
5748 return &(*EVTs->insert(VT).first);
5750 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5751 "Value type out of range!");
5752 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5756 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5757 /// indicated value. This method ignores uses of other values defined by this
5759 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5760 assert(Value < getNumValues() && "Bad value!");
5762 // TODO: Only iterate over uses of a given value of the node
5763 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5764 if (UI.getUse().getResNo() == Value) {
5771 // Found exactly the right number of uses?
5776 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5777 /// value. This method ignores uses of other values defined by this operation.
5778 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5779 assert(Value < getNumValues() && "Bad value!");
5781 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5782 if (UI.getUse().getResNo() == Value)
5789 /// isOnlyUserOf - Return true if this node is the only use of N.
5791 bool SDNode::isOnlyUserOf(SDNode *N) const {
5793 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5804 /// isOperand - Return true if this node is an operand of N.
5806 bool SDValue::isOperandOf(SDNode *N) const {
5807 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5808 if (*this == N->getOperand(i))
5813 bool SDNode::isOperandOf(SDNode *N) const {
5814 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5815 if (this == N->OperandList[i].getNode())
5820 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5821 /// be a chain) reaches the specified operand without crossing any
5822 /// side-effecting instructions on any chain path. In practice, this looks
5823 /// through token factors and non-volatile loads. In order to remain efficient,
5824 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5825 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5826 unsigned Depth) const {
5827 if (*this == Dest) return true;
5829 // Don't search too deeply, we just want to be able to see through
5830 // TokenFactor's etc.
5831 if (Depth == 0) return false;
5833 // If this is a token factor, all inputs to the TF happen in parallel. If any
5834 // of the operands of the TF does not reach dest, then we cannot do the xform.
5835 if (getOpcode() == ISD::TokenFactor) {
5836 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5837 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5842 // Loads don't have side effects, look through them.
5843 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5844 if (!Ld->isVolatile())
5845 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5850 /// hasPredecessor - Return true if N is a predecessor of this node.
5851 /// N is either an operand of this node, or can be reached by recursively
5852 /// traversing up the operands.
5853 /// NOTE: This is an expensive method. Use it carefully.
5854 bool SDNode::hasPredecessor(const SDNode *N) const {
5855 SmallPtrSet<const SDNode *, 32> Visited;
5856 SmallVector<const SDNode *, 16> Worklist;
5857 return hasPredecessorHelper(N, Visited, Worklist);
5860 bool SDNode::hasPredecessorHelper(const SDNode *N,
5861 SmallPtrSet<const SDNode *, 32> &Visited,
5862 SmallVector<const SDNode *, 16> &Worklist) const {
5863 if (Visited.empty()) {
5864 Worklist.push_back(this);
5866 // Take a look in the visited set. If we've already encountered this node
5867 // we needn't search further.
5868 if (Visited.count(N))
5872 // Haven't visited N yet. Continue the search.
5873 while (!Worklist.empty()) {
5874 const SDNode *M = Worklist.pop_back_val();
5875 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5876 SDNode *Op = M->getOperand(i).getNode();
5877 if (Visited.insert(Op))
5878 Worklist.push_back(Op);
5887 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5888 assert(Num < NumOperands && "Invalid child # of SDNode!");
5889 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5892 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
5893 assert(N->getNumValues() == 1 &&
5894 "Can't unroll a vector with multiple results!");
5896 EVT VT = N->getValueType(0);
5897 unsigned NE = VT.getVectorNumElements();
5898 EVT EltVT = VT.getVectorElementType();
5899 DebugLoc dl = N->getDebugLoc();
5901 SmallVector<SDValue, 8> Scalars;
5902 SmallVector<SDValue, 4> Operands(N->getNumOperands());
5904 // If ResNE is 0, fully unroll the vector op.
5907 else if (NE > ResNE)
5911 for (i= 0; i != NE; ++i) {
5912 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
5913 SDValue Operand = N->getOperand(j);
5914 EVT OperandVT = Operand.getValueType();
5915 if (OperandVT.isVector()) {
5916 // A vector operand; extract a single element.
5917 EVT OperandEltVT = OperandVT.getVectorElementType();
5918 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
5921 getConstant(i, TLI.getPointerTy()));
5923 // A scalar operand; just use it as is.
5924 Operands[j] = Operand;
5928 switch (N->getOpcode()) {
5930 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5931 &Operands[0], Operands.size()));
5934 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
5935 &Operands[0], Operands.size()));
5942 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
5943 getShiftAmountOperand(Operands[0].getValueType(),
5946 case ISD::SIGN_EXTEND_INREG:
5947 case ISD::FP_ROUND_INREG: {
5948 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
5949 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5951 getValueType(ExtVT)));
5956 for (; i < ResNE; ++i)
5957 Scalars.push_back(getUNDEF(EltVT));
5959 return getNode(ISD::BUILD_VECTOR, dl,
5960 EVT::getVectorVT(*getContext(), EltVT, ResNE),
5961 &Scalars[0], Scalars.size());
5965 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
5966 /// location that is 'Dist' units away from the location that the 'Base' load
5967 /// is loading from.
5968 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
5969 unsigned Bytes, int Dist) const {
5970 if (LD->getChain() != Base->getChain())
5972 EVT VT = LD->getValueType(0);
5973 if (VT.getSizeInBits() / 8 != Bytes)
5976 SDValue Loc = LD->getOperand(1);
5977 SDValue BaseLoc = Base->getOperand(1);
5978 if (Loc.getOpcode() == ISD::FrameIndex) {
5979 if (BaseLoc.getOpcode() != ISD::FrameIndex)
5981 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
5982 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
5983 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
5984 int FS = MFI->getObjectSize(FI);
5985 int BFS = MFI->getObjectSize(BFI);
5986 if (FS != BFS || FS != (int)Bytes) return false;
5987 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
5991 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
5992 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
5995 const GlobalValue *GV1 = NULL;
5996 const GlobalValue *GV2 = NULL;
5997 int64_t Offset1 = 0;
5998 int64_t Offset2 = 0;
5999 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6000 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6001 if (isGA1 && isGA2 && GV1 == GV2)
6002 return Offset1 == (Offset2 + Dist*Bytes);
6007 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6008 /// it cannot be inferred.
6009 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6010 // If this is a GlobalAddress + cst, return the alignment.
6011 const GlobalValue *GV;
6012 int64_t GVOffset = 0;
6013 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6014 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6015 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6016 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6017 TLI.getTargetData());
6018 unsigned AlignBits = KnownZero.countTrailingOnes();
6019 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6021 return MinAlign(Align, GVOffset);
6024 // If this is a direct reference to a stack slot, use information about the
6025 // stack slot's alignment.
6026 int FrameIdx = 1 << 31;
6027 int64_t FrameOffset = 0;
6028 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6029 FrameIdx = FI->getIndex();
6030 } else if (isBaseWithConstantOffset(Ptr) &&
6031 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6033 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6034 FrameOffset = Ptr.getConstantOperandVal(1);
6037 if (FrameIdx != (1 << 31)) {
6038 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6039 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6047 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6048 unsigned GlobalAddressSDNode::getAddressSpace() const {
6049 return getGlobal()->getType()->getAddressSpace();
6053 Type *ConstantPoolSDNode::getType() const {
6054 if (isMachineConstantPoolEntry())
6055 return Val.MachineCPVal->getType();
6056 return Val.ConstVal->getType();
6059 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6061 unsigned &SplatBitSize,
6063 unsigned MinSplatBits,
6065 EVT VT = getValueType(0);
6066 assert(VT.isVector() && "Expected a vector type");
6067 unsigned sz = VT.getSizeInBits();
6068 if (MinSplatBits > sz)
6071 SplatValue = APInt(sz, 0);
6072 SplatUndef = APInt(sz, 0);
6074 // Get the bits. Bits with undefined values (when the corresponding element
6075 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6076 // in SplatValue. If any of the values are not constant, give up and return
6078 unsigned int nOps = getNumOperands();
6079 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6080 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6082 for (unsigned j = 0; j < nOps; ++j) {
6083 unsigned i = isBigEndian ? nOps-1-j : j;
6084 SDValue OpVal = getOperand(i);
6085 unsigned BitPos = j * EltBitSize;
6087 if (OpVal.getOpcode() == ISD::UNDEF)
6088 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6089 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6090 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6091 zextOrTrunc(sz) << BitPos;
6092 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6093 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6098 // The build_vector is all constants or undefs. Find the smallest element
6099 // size that splats the vector.
6101 HasAnyUndefs = (SplatUndef != 0);
6104 unsigned HalfSize = sz / 2;
6105 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6106 APInt LowValue = SplatValue.trunc(HalfSize);
6107 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6108 APInt LowUndef = SplatUndef.trunc(HalfSize);
6110 // If the two halves do not match (ignoring undef bits), stop here.
6111 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6112 MinSplatBits > HalfSize)
6115 SplatValue = HighValue | LowValue;
6116 SplatUndef = HighUndef & LowUndef;
6125 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6126 // Find the first non-undef value in the shuffle mask.
6128 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6131 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6133 // Make sure all remaining elements are either undef or the same as the first
6135 for (int Idx = Mask[i]; i != e; ++i)
6136 if (Mask[i] >= 0 && Mask[i] != Idx)
6142 static void checkForCyclesHelper(const SDNode *N,
6143 SmallPtrSet<const SDNode*, 32> &Visited,
6144 SmallPtrSet<const SDNode*, 32> &Checked) {
6145 // If this node has already been checked, don't check it again.
6146 if (Checked.count(N))
6149 // If a node has already been visited on this depth-first walk, reject it as
6151 if (!Visited.insert(N)) {
6152 dbgs() << "Offending node:\n";
6154 errs() << "Detected cycle in SelectionDAG\n";
6158 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6159 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6166 void llvm::checkForCycles(const llvm::SDNode *N) {
6168 assert(N && "Checking nonexistant SDNode");
6169 SmallPtrSet<const SDNode*, 32> visited;
6170 SmallPtrSet<const SDNode*, 32> checked;
6171 checkForCyclesHelper(N, visited, checked);
6175 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6176 checkForCycles(DAG->getRoot().getNode());