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/Constants.h"
18 #include "llvm/Analysis/DebugInfo.h"
19 #include "llvm/Analysis/ValueTracking.h"
20 #include "llvm/Function.h"
21 #include "llvm/GlobalAlias.h"
22 #include "llvm/GlobalVariable.h"
23 #include "llvm/Intrinsics.h"
24 #include "llvm/DerivedTypes.h"
25 #include "llvm/Assembly/Writer.h"
26 #include "llvm/CallingConv.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::f32: return &APFloat::IEEEsingle;
66 case MVT::f64: return &APFloat::IEEEdouble;
67 case MVT::f80: return &APFloat::x87DoubleExtended;
68 case MVT::f128: return &APFloat::IEEEquad;
69 case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
73 SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
75 //===----------------------------------------------------------------------===//
76 // ConstantFPSDNode Class
77 //===----------------------------------------------------------------------===//
79 /// isExactlyValue - We don't rely on operator== working on double values, as
80 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
81 /// As such, this method can be used to do an exact bit-for-bit comparison of
82 /// two floating point values.
83 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
84 return getValueAPF().bitwiseIsEqual(V);
87 bool ConstantFPSDNode::isValueValidForType(EVT VT,
89 assert(VT.isFloatingPoint() && "Can only convert between FP types");
91 // PPC long double cannot be converted to any other type.
92 if (VT == MVT::ppcf128 ||
93 &Val.getSemantics() == &APFloat::PPCDoubleDouble)
96 // convert modifies in place, so make a copy.
97 APFloat Val2 = APFloat(Val);
99 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven,
104 //===----------------------------------------------------------------------===//
106 //===----------------------------------------------------------------------===//
108 /// isBuildVectorAllOnes - Return true if the specified node is a
109 /// BUILD_VECTOR where all of the elements are ~0 or undef.
110 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
111 // Look through a bit convert.
112 if (N->getOpcode() == ISD::BITCAST)
113 N = N->getOperand(0).getNode();
115 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
117 unsigned i = 0, e = N->getNumOperands();
119 // Skip over all of the undef values.
120 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
123 // Do not accept an all-undef vector.
124 if (i == e) return false;
126 // Do not accept build_vectors that aren't all constants or which have non-~0
127 // elements. We have to be a bit careful here, as the type of the constant
128 // may not be the same as the type of the vector elements due to type
129 // legalization (the elements are promoted to a legal type for the target and
130 // a vector of a type may be legal when the base element type is not).
131 // We only want to check enough bits to cover the vector elements, because
132 // we care if the resultant vector is all ones, not whether the individual
134 SDValue NotZero = N->getOperand(i);
135 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
136 if (isa<ConstantSDNode>(NotZero)) {
137 if (cast<ConstantSDNode>(NotZero)->getAPIntValue().countTrailingOnes() <
140 } else if (isa<ConstantFPSDNode>(NotZero)) {
141 if (cast<ConstantFPSDNode>(NotZero)->getValueAPF()
142 .bitcastToAPInt().countTrailingOnes() < EltSize)
147 // Okay, we have at least one ~0 value, check to see if the rest match or are
148 // undefs. Even with the above element type twiddling, this should be OK, as
149 // the same type legalization should have applied to all the elements.
150 for (++i; i != e; ++i)
151 if (N->getOperand(i) != NotZero &&
152 N->getOperand(i).getOpcode() != ISD::UNDEF)
158 /// isBuildVectorAllZeros - Return true if the specified node is a
159 /// BUILD_VECTOR where all of the elements are 0 or undef.
160 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
161 // Look through a bit convert.
162 if (N->getOpcode() == ISD::BITCAST)
163 N = N->getOperand(0).getNode();
165 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
167 unsigned i = 0, e = N->getNumOperands();
169 // Skip over all of the undef values.
170 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
173 // Do not accept an all-undef vector.
174 if (i == e) return false;
176 // Do not accept build_vectors that aren't all constants or which have non-0
178 SDValue Zero = N->getOperand(i);
179 if (isa<ConstantSDNode>(Zero)) {
180 if (!cast<ConstantSDNode>(Zero)->isNullValue())
182 } else if (isa<ConstantFPSDNode>(Zero)) {
183 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
188 // Okay, we have at least one 0 value, check to see if the rest match or are
190 for (++i; i != e; ++i)
191 if (N->getOperand(i) != Zero &&
192 N->getOperand(i).getOpcode() != ISD::UNDEF)
197 /// isScalarToVector - Return true if the specified node is a
198 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
199 /// element is not an undef.
200 bool ISD::isScalarToVector(const SDNode *N) {
201 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
204 if (N->getOpcode() != ISD::BUILD_VECTOR)
206 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
208 unsigned NumElems = N->getNumOperands();
211 for (unsigned i = 1; i < NumElems; ++i) {
212 SDValue V = N->getOperand(i);
213 if (V.getOpcode() != ISD::UNDEF)
219 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
220 /// when given the operation for (X op Y).
221 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
222 // To perform this operation, we just need to swap the L and G bits of the
224 unsigned OldL = (Operation >> 2) & 1;
225 unsigned OldG = (Operation >> 1) & 1;
226 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
227 (OldL << 1) | // New G bit
228 (OldG << 2)); // New L bit.
231 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
232 /// 'op' is a valid SetCC operation.
233 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
234 unsigned Operation = Op;
236 Operation ^= 7; // Flip L, G, E bits, but not U.
238 Operation ^= 15; // Flip all of the condition bits.
240 if (Operation > ISD::SETTRUE2)
241 Operation &= ~8; // Don't let N and U bits get set.
243 return ISD::CondCode(Operation);
247 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
248 /// signed operation and 2 if the result is an unsigned comparison. Return zero
249 /// if the operation does not depend on the sign of the input (setne and seteq).
250 static int isSignedOp(ISD::CondCode Opcode) {
252 default: llvm_unreachable("Illegal integer setcc operation!");
254 case ISD::SETNE: return 0;
258 case ISD::SETGE: return 1;
262 case ISD::SETUGE: return 2;
266 /// getSetCCOrOperation - Return the result of a logical OR between different
267 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
268 /// returns SETCC_INVALID if it is not possible to represent the resultant
270 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
272 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
273 // Cannot fold a signed integer setcc with an unsigned integer setcc.
274 return ISD::SETCC_INVALID;
276 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
278 // If the N and U bits get set then the resultant comparison DOES suddenly
279 // care about orderedness, and is true when ordered.
280 if (Op > ISD::SETTRUE2)
281 Op &= ~16; // Clear the U bit if the N bit is set.
283 // Canonicalize illegal integer setcc's.
284 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
287 return ISD::CondCode(Op);
290 /// getSetCCAndOperation - Return the result of a logical AND between different
291 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
292 /// function returns zero if it is not possible to represent the resultant
294 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
296 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
297 // Cannot fold a signed setcc with an unsigned setcc.
298 return ISD::SETCC_INVALID;
300 // Combine all of the condition bits.
301 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
303 // Canonicalize illegal integer setcc's.
307 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
308 case ISD::SETOEQ: // SETEQ & SETU[LG]E
309 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
310 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
311 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
318 //===----------------------------------------------------------------------===//
319 // SDNode Profile Support
320 //===----------------------------------------------------------------------===//
322 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
324 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
328 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
329 /// solely with their pointer.
330 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
331 ID.AddPointer(VTList.VTs);
334 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
336 static void AddNodeIDOperands(FoldingSetNodeID &ID,
337 const SDValue *Ops, unsigned NumOps) {
338 for (; NumOps; --NumOps, ++Ops) {
339 ID.AddPointer(Ops->getNode());
340 ID.AddInteger(Ops->getResNo());
344 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
346 static void AddNodeIDOperands(FoldingSetNodeID &ID,
347 const SDUse *Ops, unsigned NumOps) {
348 for (; NumOps; --NumOps, ++Ops) {
349 ID.AddPointer(Ops->getNode());
350 ID.AddInteger(Ops->getResNo());
354 static void AddNodeIDNode(FoldingSetNodeID &ID,
355 unsigned short OpC, SDVTList VTList,
356 const SDValue *OpList, unsigned N) {
357 AddNodeIDOpcode(ID, OpC);
358 AddNodeIDValueTypes(ID, VTList);
359 AddNodeIDOperands(ID, OpList, N);
362 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
364 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
365 switch (N->getOpcode()) {
366 case ISD::TargetExternalSymbol:
367 case ISD::ExternalSymbol:
368 llvm_unreachable("Should only be used on nodes with operands");
369 default: break; // Normal nodes don't need extra info.
370 case ISD::TargetConstant:
372 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
374 case ISD::TargetConstantFP:
375 case ISD::ConstantFP: {
376 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
379 case ISD::TargetGlobalAddress:
380 case ISD::GlobalAddress:
381 case ISD::TargetGlobalTLSAddress:
382 case ISD::GlobalTLSAddress: {
383 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
384 ID.AddPointer(GA->getGlobal());
385 ID.AddInteger(GA->getOffset());
386 ID.AddInteger(GA->getTargetFlags());
389 case ISD::BasicBlock:
390 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
393 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
395 case ISD::RegisterMask:
396 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
399 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
401 case ISD::FrameIndex:
402 case ISD::TargetFrameIndex:
403 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
406 case ISD::TargetJumpTable:
407 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
408 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
410 case ISD::ConstantPool:
411 case ISD::TargetConstantPool: {
412 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
413 ID.AddInteger(CP->getAlignment());
414 ID.AddInteger(CP->getOffset());
415 if (CP->isMachineConstantPoolEntry())
416 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
418 ID.AddPointer(CP->getConstVal());
419 ID.AddInteger(CP->getTargetFlags());
423 const LoadSDNode *LD = cast<LoadSDNode>(N);
424 ID.AddInteger(LD->getMemoryVT().getRawBits());
425 ID.AddInteger(LD->getRawSubclassData());
429 const StoreSDNode *ST = cast<StoreSDNode>(N);
430 ID.AddInteger(ST->getMemoryVT().getRawBits());
431 ID.AddInteger(ST->getRawSubclassData());
434 case ISD::ATOMIC_CMP_SWAP:
435 case ISD::ATOMIC_SWAP:
436 case ISD::ATOMIC_LOAD_ADD:
437 case ISD::ATOMIC_LOAD_SUB:
438 case ISD::ATOMIC_LOAD_AND:
439 case ISD::ATOMIC_LOAD_OR:
440 case ISD::ATOMIC_LOAD_XOR:
441 case ISD::ATOMIC_LOAD_NAND:
442 case ISD::ATOMIC_LOAD_MIN:
443 case ISD::ATOMIC_LOAD_MAX:
444 case ISD::ATOMIC_LOAD_UMIN:
445 case ISD::ATOMIC_LOAD_UMAX:
446 case ISD::ATOMIC_LOAD:
447 case ISD::ATOMIC_STORE: {
448 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
449 ID.AddInteger(AT->getMemoryVT().getRawBits());
450 ID.AddInteger(AT->getRawSubclassData());
453 case ISD::VECTOR_SHUFFLE: {
454 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
455 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
457 ID.AddInteger(SVN->getMaskElt(i));
460 case ISD::TargetBlockAddress:
461 case ISD::BlockAddress: {
462 ID.AddPointer(cast<BlockAddressSDNode>(N)->getBlockAddress());
463 ID.AddInteger(cast<BlockAddressSDNode>(N)->getTargetFlags());
466 } // end switch (N->getOpcode())
469 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
471 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
472 AddNodeIDOpcode(ID, N->getOpcode());
473 // Add the return value info.
474 AddNodeIDValueTypes(ID, N->getVTList());
475 // Add the operand info.
476 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
478 // Handle SDNode leafs with special info.
479 AddNodeIDCustom(ID, N);
482 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
483 /// the CSE map that carries volatility, temporalness, indexing mode, and
484 /// extension/truncation information.
486 static inline unsigned
487 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
488 bool isNonTemporal, bool isInvariant) {
489 assert((ConvType & 3) == ConvType &&
490 "ConvType may not require more than 2 bits!");
491 assert((AM & 7) == AM &&
492 "AM may not require more than 3 bits!");
496 (isNonTemporal << 6) |
500 //===----------------------------------------------------------------------===//
501 // SelectionDAG Class
502 //===----------------------------------------------------------------------===//
504 /// doNotCSE - Return true if CSE should not be performed for this node.
505 static bool doNotCSE(SDNode *N) {
506 if (N->getValueType(0) == MVT::Glue)
507 return true; // Never CSE anything that produces a flag.
509 switch (N->getOpcode()) {
511 case ISD::HANDLENODE:
513 return true; // Never CSE these nodes.
516 // Check that remaining values produced are not flags.
517 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
518 if (N->getValueType(i) == MVT::Glue)
519 return true; // Never CSE anything that produces a flag.
524 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
526 void SelectionDAG::RemoveDeadNodes() {
527 // Create a dummy node (which is not added to allnodes), that adds a reference
528 // to the root node, preventing it from being deleted.
529 HandleSDNode Dummy(getRoot());
531 SmallVector<SDNode*, 128> DeadNodes;
533 // Add all obviously-dead nodes to the DeadNodes worklist.
534 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
536 DeadNodes.push_back(I);
538 RemoveDeadNodes(DeadNodes);
540 // If the root changed (e.g. it was a dead load, update the root).
541 setRoot(Dummy.getValue());
544 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
545 /// given list, and any nodes that become unreachable as a result.
546 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
547 DAGUpdateListener *UpdateListener) {
549 // Process the worklist, deleting the nodes and adding their uses to the
551 while (!DeadNodes.empty()) {
552 SDNode *N = DeadNodes.pop_back_val();
555 UpdateListener->NodeDeleted(N, 0);
557 // Take the node out of the appropriate CSE map.
558 RemoveNodeFromCSEMaps(N);
560 // Next, brutally remove the operand list. This is safe to do, as there are
561 // no cycles in the graph.
562 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
564 SDNode *Operand = Use.getNode();
567 // Now that we removed this operand, see if there are no uses of it left.
568 if (Operand->use_empty())
569 DeadNodes.push_back(Operand);
576 void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
577 SmallVector<SDNode*, 16> DeadNodes(1, N);
579 // Create a dummy node that adds a reference to the root node, preventing
580 // it from being deleted. (This matters if the root is an operand of the
582 HandleSDNode Dummy(getRoot());
584 RemoveDeadNodes(DeadNodes, UpdateListener);
587 void SelectionDAG::DeleteNode(SDNode *N) {
588 // First take this out of the appropriate CSE map.
589 RemoveNodeFromCSEMaps(N);
591 // Finally, remove uses due to operands of this node, remove from the
592 // AllNodes list, and delete the node.
593 DeleteNodeNotInCSEMaps(N);
596 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
597 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
598 assert(N->use_empty() && "Cannot delete a node that is not dead!");
600 // Drop all of the operands and decrement used node's use counts.
606 void SelectionDAG::DeallocateNode(SDNode *N) {
607 if (N->OperandsNeedDelete)
608 delete[] N->OperandList;
610 // Set the opcode to DELETED_NODE to help catch bugs when node
611 // memory is reallocated.
612 N->NodeType = ISD::DELETED_NODE;
614 NodeAllocator.Deallocate(AllNodes.remove(N));
616 // Remove the ordering of this node.
619 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
620 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
621 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
622 DbgVals[i]->setIsInvalidated();
625 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
626 /// correspond to it. This is useful when we're about to delete or repurpose
627 /// the node. We don't want future request for structurally identical nodes
628 /// to return N anymore.
629 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
631 switch (N->getOpcode()) {
632 case ISD::HANDLENODE: return false; // noop.
634 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
635 "Cond code doesn't exist!");
636 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
637 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
639 case ISD::ExternalSymbol:
640 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
642 case ISD::TargetExternalSymbol: {
643 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
644 Erased = TargetExternalSymbols.erase(
645 std::pair<std::string,unsigned char>(ESN->getSymbol(),
646 ESN->getTargetFlags()));
649 case ISD::VALUETYPE: {
650 EVT VT = cast<VTSDNode>(N)->getVT();
651 if (VT.isExtended()) {
652 Erased = ExtendedValueTypeNodes.erase(VT);
654 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
655 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
660 // Remove it from the CSE Map.
661 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
662 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
663 Erased = CSEMap.RemoveNode(N);
667 // Verify that the node was actually in one of the CSE maps, unless it has a
668 // flag result (which cannot be CSE'd) or is one of the special cases that are
669 // not subject to CSE.
670 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
671 !N->isMachineOpcode() && !doNotCSE(N)) {
674 llvm_unreachable("Node is not in map!");
680 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
681 /// maps and modified in place. Add it back to the CSE maps, unless an identical
682 /// node already exists, in which case transfer all its users to the existing
683 /// node. This transfer can potentially trigger recursive merging.
686 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N,
687 DAGUpdateListener *UpdateListener) {
688 // For node types that aren't CSE'd, just act as if no identical node
691 SDNode *Existing = CSEMap.GetOrInsertNode(N);
693 // If there was already an existing matching node, use ReplaceAllUsesWith
694 // to replace the dead one with the existing one. This can cause
695 // recursive merging of other unrelated nodes down the line.
696 ReplaceAllUsesWith(N, Existing, UpdateListener);
698 // N is now dead. Inform the listener if it exists and delete it.
700 UpdateListener->NodeDeleted(N, Existing);
701 DeleteNodeNotInCSEMaps(N);
706 // If the node doesn't already exist, we updated it. Inform a listener if
709 UpdateListener->NodeUpdated(N);
712 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
713 /// were replaced with those specified. If this node is never memoized,
714 /// return null, otherwise return a pointer to the slot it would take. If a
715 /// node already exists with these operands, the slot will be non-null.
716 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
721 SDValue Ops[] = { Op };
723 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
724 AddNodeIDCustom(ID, N);
725 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
729 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
730 /// were replaced with those specified. If this node is never memoized,
731 /// return null, otherwise return a pointer to the slot it would take. If a
732 /// node already exists with these operands, the slot will be non-null.
733 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
734 SDValue Op1, SDValue Op2,
739 SDValue Ops[] = { Op1, Op2 };
741 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
742 AddNodeIDCustom(ID, N);
743 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
748 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
749 /// were replaced with those specified. If this node is never memoized,
750 /// return null, otherwise return a pointer to the slot it would take. If a
751 /// node already exists with these operands, the slot will be non-null.
752 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
753 const SDValue *Ops,unsigned NumOps,
759 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
760 AddNodeIDCustom(ID, N);
761 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
766 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
767 static void VerifyNodeCommon(SDNode *N) {
768 switch (N->getOpcode()) {
771 case ISD::BUILD_PAIR: {
772 EVT VT = N->getValueType(0);
773 assert(N->getNumValues() == 1 && "Too many results!");
774 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
775 "Wrong return type!");
776 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
777 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
778 "Mismatched operand types!");
779 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
780 "Wrong operand type!");
781 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
782 "Wrong return type size");
785 case ISD::BUILD_VECTOR: {
786 assert(N->getNumValues() == 1 && "Too many results!");
787 assert(N->getValueType(0).isVector() && "Wrong return type!");
788 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
789 "Wrong number of operands!");
790 EVT EltVT = N->getValueType(0).getVectorElementType();
791 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
792 assert((I->getValueType() == EltVT ||
793 (EltVT.isInteger() && I->getValueType().isInteger() &&
794 EltVT.bitsLE(I->getValueType()))) &&
795 "Wrong operand type!");
796 assert(I->getValueType() == N->getOperand(0).getValueType() &&
797 "Operands must all have the same type");
804 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
805 static void VerifySDNode(SDNode *N) {
806 // The SDNode allocators cannot be used to allocate nodes with fields that are
807 // not present in an SDNode!
808 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
809 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
810 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
811 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
812 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
813 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
814 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
815 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
816 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
817 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
818 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
819 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
820 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
821 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
822 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
823 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
824 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
825 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
826 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
831 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
833 static void VerifyMachineNode(SDNode *N) {
834 // The MachineNode allocators cannot be used to allocate nodes with fields
835 // that are not present in a MachineNode!
836 // Currently there are no such nodes.
842 /// getEVTAlignment - Compute the default alignment value for the
845 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
846 Type *Ty = VT == MVT::iPTR ?
847 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
848 VT.getTypeForEVT(*getContext());
850 return TLI.getTargetData()->getABITypeAlignment(Ty);
853 // EntryNode could meaningfully have debug info if we can find it...
854 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
855 : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
856 OptLevel(OL), EntryNode(ISD::EntryToken, DebugLoc(), getVTList(MVT::Other)),
857 Root(getEntryNode()), Ordering(0) {
858 AllNodes.push_back(&EntryNode);
859 Ordering = new SDNodeOrdering();
860 DbgInfo = new SDDbgInfo();
863 void SelectionDAG::init(MachineFunction &mf) {
865 Context = &mf.getFunction()->getContext();
868 SelectionDAG::~SelectionDAG() {
874 void SelectionDAG::allnodes_clear() {
875 assert(&*AllNodes.begin() == &EntryNode);
876 AllNodes.remove(AllNodes.begin());
877 while (!AllNodes.empty())
878 DeallocateNode(AllNodes.begin());
881 void SelectionDAG::clear() {
883 OperandAllocator.Reset();
886 ExtendedValueTypeNodes.clear();
887 ExternalSymbols.clear();
888 TargetExternalSymbols.clear();
889 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
890 static_cast<CondCodeSDNode*>(0));
891 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
892 static_cast<SDNode*>(0));
894 EntryNode.UseList = 0;
895 AllNodes.push_back(&EntryNode);
896 Root = getEntryNode();
901 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
902 return VT.bitsGT(Op.getValueType()) ?
903 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
904 getNode(ISD::TRUNCATE, DL, VT, Op);
907 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
908 return VT.bitsGT(Op.getValueType()) ?
909 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
910 getNode(ISD::TRUNCATE, DL, VT, Op);
913 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
914 return VT.bitsGT(Op.getValueType()) ?
915 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
916 getNode(ISD::TRUNCATE, DL, VT, Op);
919 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
920 assert(!VT.isVector() &&
921 "getZeroExtendInReg should use the vector element type instead of "
923 if (Op.getValueType() == VT) return Op;
924 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
925 APInt Imm = APInt::getLowBitsSet(BitWidth,
927 return getNode(ISD::AND, DL, Op.getValueType(), Op,
928 getConstant(Imm, Op.getValueType()));
931 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
933 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
934 EVT EltVT = VT.getScalarType();
936 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
937 return getNode(ISD::XOR, DL, VT, Val, NegOne);
940 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
941 EVT EltVT = VT.getScalarType();
942 assert((EltVT.getSizeInBits() >= 64 ||
943 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
944 "getConstant with a uint64_t value that doesn't fit in the type!");
945 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
948 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
949 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
952 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
953 assert(VT.isInteger() && "Cannot create FP integer constant!");
955 EVT EltVT = VT.getScalarType();
956 const ConstantInt *Elt = &Val;
958 // In some cases the vector type is legal but the element type is illegal and
959 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
960 // inserted value (the type does not need to match the vector element type).
961 // Any extra bits introduced will be truncated away.
962 if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
963 TargetLowering::TypePromoteInteger) {
964 EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
965 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
966 Elt = ConstantInt::get(*getContext(), NewVal);
969 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
970 "APInt size does not match type size!");
971 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
973 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
977 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
979 return SDValue(N, 0);
982 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
983 CSEMap.InsertNode(N, IP);
984 AllNodes.push_back(N);
987 SDValue Result(N, 0);
989 SmallVector<SDValue, 8> Ops;
990 Ops.assign(VT.getVectorNumElements(), Result);
991 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
996 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
997 return getConstant(Val, TLI.getPointerTy(), isTarget);
1001 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1002 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1005 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1006 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1008 EVT EltVT = VT.getScalarType();
1010 // Do the map lookup using the actual bit pattern for the floating point
1011 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1012 // we don't have issues with SNANs.
1013 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1014 FoldingSetNodeID ID;
1015 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1019 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1021 return SDValue(N, 0);
1024 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1025 CSEMap.InsertNode(N, IP);
1026 AllNodes.push_back(N);
1029 SDValue Result(N, 0);
1030 if (VT.isVector()) {
1031 SmallVector<SDValue, 8> Ops;
1032 Ops.assign(VT.getVectorNumElements(), Result);
1033 // FIXME DebugLoc info might be appropriate here
1034 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1039 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1040 EVT EltVT = VT.getScalarType();
1041 if (EltVT==MVT::f32)
1042 return getConstantFP(APFloat((float)Val), VT, isTarget);
1043 else if (EltVT==MVT::f64)
1044 return getConstantFP(APFloat(Val), VT, isTarget);
1045 else if (EltVT==MVT::f80 || EltVT==MVT::f128) {
1047 APFloat apf = APFloat(Val);
1048 apf.convert(*EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1050 return getConstantFP(apf, VT, isTarget);
1052 llvm_unreachable("Unsupported type in getConstantFP");
1055 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1056 EVT VT, int64_t Offset,
1058 unsigned char TargetFlags) {
1059 assert((TargetFlags == 0 || isTargetGA) &&
1060 "Cannot set target flags on target-independent globals");
1062 // Truncate (with sign-extension) the offset value to the pointer size.
1063 EVT PTy = TLI.getPointerTy();
1064 unsigned BitWidth = PTy.getSizeInBits();
1066 Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth));
1068 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1070 // If GV is an alias then use the aliasee for determining thread-localness.
1071 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1072 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1076 if (GVar && GVar->isThreadLocal())
1077 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1079 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1081 FoldingSetNodeID ID;
1082 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1084 ID.AddInteger(Offset);
1085 ID.AddInteger(TargetFlags);
1087 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1088 return SDValue(E, 0);
1090 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1091 Offset, TargetFlags);
1092 CSEMap.InsertNode(N, IP);
1093 AllNodes.push_back(N);
1094 return SDValue(N, 0);
1097 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1098 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1099 FoldingSetNodeID ID;
1100 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1103 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1104 return SDValue(E, 0);
1106 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1107 CSEMap.InsertNode(N, IP);
1108 AllNodes.push_back(N);
1109 return SDValue(N, 0);
1112 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1113 unsigned char TargetFlags) {
1114 assert((TargetFlags == 0 || isTarget) &&
1115 "Cannot set target flags on target-independent jump tables");
1116 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1117 FoldingSetNodeID ID;
1118 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1120 ID.AddInteger(TargetFlags);
1122 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1123 return SDValue(E, 0);
1125 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1127 CSEMap.InsertNode(N, IP);
1128 AllNodes.push_back(N);
1129 return SDValue(N, 0);
1132 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1133 unsigned Alignment, int Offset,
1135 unsigned char TargetFlags) {
1136 assert((TargetFlags == 0 || isTarget) &&
1137 "Cannot set target flags on target-independent globals");
1139 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1140 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1141 FoldingSetNodeID ID;
1142 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1143 ID.AddInteger(Alignment);
1144 ID.AddInteger(Offset);
1146 ID.AddInteger(TargetFlags);
1148 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1149 return SDValue(E, 0);
1151 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1152 Alignment, TargetFlags);
1153 CSEMap.InsertNode(N, IP);
1154 AllNodes.push_back(N);
1155 return SDValue(N, 0);
1159 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1160 unsigned Alignment, int Offset,
1162 unsigned char TargetFlags) {
1163 assert((TargetFlags == 0 || isTarget) &&
1164 "Cannot set target flags on target-independent globals");
1166 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1167 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1168 FoldingSetNodeID ID;
1169 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1170 ID.AddInteger(Alignment);
1171 ID.AddInteger(Offset);
1172 C->addSelectionDAGCSEId(ID);
1173 ID.AddInteger(TargetFlags);
1175 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1176 return SDValue(E, 0);
1178 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1179 Alignment, TargetFlags);
1180 CSEMap.InsertNode(N, IP);
1181 AllNodes.push_back(N);
1182 return SDValue(N, 0);
1185 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1186 FoldingSetNodeID ID;
1187 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1190 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1191 return SDValue(E, 0);
1193 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1194 CSEMap.InsertNode(N, IP);
1195 AllNodes.push_back(N);
1196 return SDValue(N, 0);
1199 SDValue SelectionDAG::getValueType(EVT VT) {
1200 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1201 ValueTypeNodes.size())
1202 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1204 SDNode *&N = VT.isExtended() ?
1205 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1207 if (N) return SDValue(N, 0);
1208 N = new (NodeAllocator) VTSDNode(VT);
1209 AllNodes.push_back(N);
1210 return SDValue(N, 0);
1213 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1214 SDNode *&N = ExternalSymbols[Sym];
1215 if (N) return SDValue(N, 0);
1216 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1217 AllNodes.push_back(N);
1218 return SDValue(N, 0);
1221 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1222 unsigned char TargetFlags) {
1224 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1226 if (N) return SDValue(N, 0);
1227 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1228 AllNodes.push_back(N);
1229 return SDValue(N, 0);
1232 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1233 if ((unsigned)Cond >= CondCodeNodes.size())
1234 CondCodeNodes.resize(Cond+1);
1236 if (CondCodeNodes[Cond] == 0) {
1237 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1238 CondCodeNodes[Cond] = N;
1239 AllNodes.push_back(N);
1242 return SDValue(CondCodeNodes[Cond], 0);
1245 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1246 // the shuffle mask M that point at N1 to point at N2, and indices that point
1247 // N2 to point at N1.
1248 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1250 int NElts = M.size();
1251 for (int i = 0; i != NElts; ++i) {
1259 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1260 SDValue N2, const int *Mask) {
1261 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1262 assert(VT.isVector() && N1.getValueType().isVector() &&
1263 "Vector Shuffle VTs must be a vectors");
1264 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1265 && "Vector Shuffle VTs must have same element type");
1267 // Canonicalize shuffle undef, undef -> undef
1268 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1269 return getUNDEF(VT);
1271 // Validate that all indices in Mask are within the range of the elements
1272 // input to the shuffle.
1273 unsigned NElts = VT.getVectorNumElements();
1274 SmallVector<int, 8> MaskVec;
1275 for (unsigned i = 0; i != NElts; ++i) {
1276 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1277 MaskVec.push_back(Mask[i]);
1280 // Canonicalize shuffle v, v -> v, undef
1283 for (unsigned i = 0; i != NElts; ++i)
1284 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1287 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1288 if (N1.getOpcode() == ISD::UNDEF)
1289 commuteShuffle(N1, N2, MaskVec);
1291 // Canonicalize all index into lhs, -> shuffle lhs, undef
1292 // Canonicalize all index into rhs, -> shuffle rhs, undef
1293 bool AllLHS = true, AllRHS = true;
1294 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1295 for (unsigned i = 0; i != NElts; ++i) {
1296 if (MaskVec[i] >= (int)NElts) {
1301 } else if (MaskVec[i] >= 0) {
1305 if (AllLHS && AllRHS)
1306 return getUNDEF(VT);
1307 if (AllLHS && !N2Undef)
1311 commuteShuffle(N1, N2, MaskVec);
1314 // If Identity shuffle, or all shuffle in to undef, return that node.
1315 bool AllUndef = true;
1316 bool Identity = true;
1317 for (unsigned i = 0; i != NElts; ++i) {
1318 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1319 if (MaskVec[i] >= 0) AllUndef = false;
1321 if (Identity && NElts == N1.getValueType().getVectorNumElements())
1324 return getUNDEF(VT);
1326 FoldingSetNodeID ID;
1327 SDValue Ops[2] = { N1, N2 };
1328 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1329 for (unsigned i = 0; i != NElts; ++i)
1330 ID.AddInteger(MaskVec[i]);
1333 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1334 return SDValue(E, 0);
1336 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1337 // SDNode doesn't have access to it. This memory will be "leaked" when
1338 // the node is deallocated, but recovered when the NodeAllocator is released.
1339 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1340 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1342 ShuffleVectorSDNode *N =
1343 new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1344 CSEMap.InsertNode(N, IP);
1345 AllNodes.push_back(N);
1346 return SDValue(N, 0);
1349 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1350 SDValue Val, SDValue DTy,
1351 SDValue STy, SDValue Rnd, SDValue Sat,
1352 ISD::CvtCode Code) {
1353 // If the src and dest types are the same and the conversion is between
1354 // integer types of the same sign or two floats, no conversion is necessary.
1356 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1359 FoldingSetNodeID ID;
1360 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1361 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1363 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1364 return SDValue(E, 0);
1366 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1368 CSEMap.InsertNode(N, IP);
1369 AllNodes.push_back(N);
1370 return SDValue(N, 0);
1373 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1374 FoldingSetNodeID ID;
1375 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1376 ID.AddInteger(RegNo);
1378 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1379 return SDValue(E, 0);
1381 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1382 CSEMap.InsertNode(N, IP);
1383 AllNodes.push_back(N);
1384 return SDValue(N, 0);
1387 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1388 FoldingSetNodeID ID;
1389 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1390 ID.AddPointer(RegMask);
1392 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1393 return SDValue(E, 0);
1395 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1396 CSEMap.InsertNode(N, IP);
1397 AllNodes.push_back(N);
1398 return SDValue(N, 0);
1401 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1402 FoldingSetNodeID ID;
1403 SDValue Ops[] = { Root };
1404 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1405 ID.AddPointer(Label);
1407 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1408 return SDValue(E, 0);
1410 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1411 CSEMap.InsertNode(N, IP);
1412 AllNodes.push_back(N);
1413 return SDValue(N, 0);
1417 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1419 unsigned char TargetFlags) {
1420 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1422 FoldingSetNodeID ID;
1423 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1425 ID.AddInteger(TargetFlags);
1427 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1428 return SDValue(E, 0);
1430 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, TargetFlags);
1431 CSEMap.InsertNode(N, IP);
1432 AllNodes.push_back(N);
1433 return SDValue(N, 0);
1436 SDValue SelectionDAG::getSrcValue(const Value *V) {
1437 assert((!V || V->getType()->isPointerTy()) &&
1438 "SrcValue is not a pointer?");
1440 FoldingSetNodeID ID;
1441 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1445 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1446 return SDValue(E, 0);
1448 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1449 CSEMap.InsertNode(N, IP);
1450 AllNodes.push_back(N);
1451 return SDValue(N, 0);
1454 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1455 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1456 FoldingSetNodeID ID;
1457 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1461 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1462 return SDValue(E, 0);
1464 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1465 CSEMap.InsertNode(N, IP);
1466 AllNodes.push_back(N);
1467 return SDValue(N, 0);
1471 /// getShiftAmountOperand - Return the specified value casted to
1472 /// the target's desired shift amount type.
1473 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1474 EVT OpTy = Op.getValueType();
1475 MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1476 if (OpTy == ShTy || OpTy.isVector()) return Op;
1478 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1479 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1482 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1483 /// specified value type.
1484 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1485 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1486 unsigned ByteSize = VT.getStoreSize();
1487 Type *Ty = VT.getTypeForEVT(*getContext());
1488 unsigned StackAlign =
1489 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1491 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1492 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1495 /// CreateStackTemporary - Create a stack temporary suitable for holding
1496 /// either of the specified value types.
1497 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1498 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1499 VT2.getStoreSizeInBits())/8;
1500 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1501 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1502 const TargetData *TD = TLI.getTargetData();
1503 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1504 TD->getPrefTypeAlignment(Ty2));
1506 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1507 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1508 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1511 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1512 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1513 // These setcc operations always fold.
1517 case ISD::SETFALSE2: return getConstant(0, VT);
1519 case ISD::SETTRUE2: return getConstant(1, VT);
1531 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1535 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1536 const APInt &C2 = N2C->getAPIntValue();
1537 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1538 const APInt &C1 = N1C->getAPIntValue();
1541 default: llvm_unreachable("Unknown integer setcc!");
1542 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1543 case ISD::SETNE: return getConstant(C1 != C2, VT);
1544 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1545 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1546 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1547 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1548 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1549 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1550 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1551 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1555 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1556 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1557 // No compile time operations on this type yet.
1558 if (N1C->getValueType(0) == MVT::ppcf128)
1561 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1564 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1565 return getUNDEF(VT);
1567 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1568 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1569 return getUNDEF(VT);
1571 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1572 R==APFloat::cmpLessThan, VT);
1573 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1574 return getUNDEF(VT);
1576 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1577 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1578 return getUNDEF(VT);
1580 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1581 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1582 return getUNDEF(VT);
1584 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1585 R==APFloat::cmpEqual, VT);
1586 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1587 return getUNDEF(VT);
1589 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1590 R==APFloat::cmpEqual, VT);
1591 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1592 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1593 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1594 R==APFloat::cmpEqual, VT);
1595 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1596 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1597 R==APFloat::cmpLessThan, VT);
1598 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1599 R==APFloat::cmpUnordered, VT);
1600 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1601 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1604 // Ensure that the constant occurs on the RHS.
1605 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1609 // Could not fold it.
1613 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1614 /// use this predicate to simplify operations downstream.
1615 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1616 // This predicate is not safe for vector operations.
1617 if (Op.getValueType().isVector())
1620 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1621 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1624 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1625 /// this predicate to simplify operations downstream. Mask is known to be zero
1626 /// for bits that V cannot have.
1627 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1628 unsigned Depth) const {
1629 APInt KnownZero, KnownOne;
1630 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1631 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1632 return (KnownZero & Mask) == Mask;
1635 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1636 /// known to be either zero or one and return them in the KnownZero/KnownOne
1637 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1639 void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask,
1640 APInt &KnownZero, APInt &KnownOne,
1641 unsigned Depth) const {
1642 unsigned BitWidth = Mask.getBitWidth();
1643 assert(BitWidth == Op.getValueType().getScalarType().getSizeInBits() &&
1644 "Mask size mismatches value type size!");
1646 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1647 if (Depth == 6 || Mask == 0)
1648 return; // Limit search depth.
1650 APInt KnownZero2, KnownOne2;
1652 switch (Op.getOpcode()) {
1654 // We know all of the bits for a constant!
1655 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask;
1656 KnownZero = ~KnownOne & Mask;
1659 // If either the LHS or the RHS are Zero, the result is zero.
1660 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1661 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero,
1662 KnownZero2, KnownOne2, Depth+1);
1663 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1664 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1666 // Output known-1 bits are only known if set in both the LHS & RHS.
1667 KnownOne &= KnownOne2;
1668 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1669 KnownZero |= KnownZero2;
1672 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1673 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne,
1674 KnownZero2, KnownOne2, Depth+1);
1675 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1676 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1678 // Output known-0 bits are only known if clear in both the LHS & RHS.
1679 KnownZero &= KnownZero2;
1680 // Output known-1 are known to be set if set in either the LHS | RHS.
1681 KnownOne |= KnownOne2;
1684 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1685 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
1686 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1687 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1689 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1690 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1691 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1692 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1693 KnownZero = KnownZeroOut;
1697 APInt Mask2 = APInt::getAllOnesValue(BitWidth);
1698 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero, KnownOne, Depth+1);
1699 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1700 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1701 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1703 // If low bits are zero in either operand, output low known-0 bits.
1704 // Also compute a conserative estimate for high known-0 bits.
1705 // More trickiness is possible, but this is sufficient for the
1706 // interesting case of alignment computation.
1707 KnownOne.clearAllBits();
1708 unsigned TrailZ = KnownZero.countTrailingOnes() +
1709 KnownZero2.countTrailingOnes();
1710 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1711 KnownZero2.countLeadingOnes(),
1712 BitWidth) - BitWidth;
1714 TrailZ = std::min(TrailZ, BitWidth);
1715 LeadZ = std::min(LeadZ, BitWidth);
1716 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1717 APInt::getHighBitsSet(BitWidth, LeadZ);
1722 // For the purposes of computing leading zeros we can conservatively
1723 // treat a udiv as a logical right shift by the power of 2 known to
1724 // be less than the denominator.
1725 APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1726 ComputeMaskedBits(Op.getOperand(0),
1727 AllOnes, KnownZero2, KnownOne2, Depth+1);
1728 unsigned LeadZ = KnownZero2.countLeadingOnes();
1730 KnownOne2.clearAllBits();
1731 KnownZero2.clearAllBits();
1732 ComputeMaskedBits(Op.getOperand(1),
1733 AllOnes, KnownZero2, KnownOne2, Depth+1);
1734 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1735 if (RHSUnknownLeadingOnes != BitWidth)
1736 LeadZ = std::min(BitWidth,
1737 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1739 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
1743 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
1744 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
1745 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1746 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1748 // Only known if known in both the LHS and RHS.
1749 KnownOne &= KnownOne2;
1750 KnownZero &= KnownZero2;
1752 case ISD::SELECT_CC:
1753 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
1754 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
1755 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1756 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1758 // Only known if known in both the LHS and RHS.
1759 KnownOne &= KnownOne2;
1760 KnownZero &= KnownZero2;
1768 if (Op.getResNo() != 1)
1770 // The boolean result conforms to getBooleanContents. Fall through.
1772 // If we know the result of a setcc has the top bits zero, use this info.
1773 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1774 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1775 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1778 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1779 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1780 unsigned ShAmt = SA->getZExtValue();
1782 // If the shift count is an invalid immediate, don't do anything.
1783 if (ShAmt >= BitWidth)
1786 ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt),
1787 KnownZero, KnownOne, Depth+1);
1788 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1789 KnownZero <<= ShAmt;
1791 // low bits known zero.
1792 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1796 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1797 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1798 unsigned ShAmt = SA->getZExtValue();
1800 // If the shift count is an invalid immediate, don't do anything.
1801 if (ShAmt >= BitWidth)
1804 ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt),
1805 KnownZero, KnownOne, Depth+1);
1806 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1807 KnownZero = KnownZero.lshr(ShAmt);
1808 KnownOne = KnownOne.lshr(ShAmt);
1810 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1811 KnownZero |= HighBits; // High bits known zero.
1815 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1816 unsigned ShAmt = SA->getZExtValue();
1818 // If the shift count is an invalid immediate, don't do anything.
1819 if (ShAmt >= BitWidth)
1822 APInt InDemandedMask = (Mask << ShAmt);
1823 // If any of the demanded bits are produced by the sign extension, we also
1824 // demand the input sign bit.
1825 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1826 if (HighBits.getBoolValue())
1827 InDemandedMask |= APInt::getSignBit(BitWidth);
1829 ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne,
1831 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1832 KnownZero = KnownZero.lshr(ShAmt);
1833 KnownOne = KnownOne.lshr(ShAmt);
1835 // Handle the sign bits.
1836 APInt SignBit = APInt::getSignBit(BitWidth);
1837 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1839 if (KnownZero.intersects(SignBit)) {
1840 KnownZero |= HighBits; // New bits are known zero.
1841 } else if (KnownOne.intersects(SignBit)) {
1842 KnownOne |= HighBits; // New bits are known one.
1846 case ISD::SIGN_EXTEND_INREG: {
1847 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1848 unsigned EBits = EVT.getScalarType().getSizeInBits();
1850 // Sign extension. Compute the demanded bits in the result that are not
1851 // present in the input.
1852 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask;
1854 APInt InSignBit = APInt::getSignBit(EBits);
1855 APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits);
1857 // If the sign extended bits are demanded, we know that the sign
1859 InSignBit = InSignBit.zext(BitWidth);
1860 if (NewBits.getBoolValue())
1861 InputDemandedBits |= InSignBit;
1863 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
1864 KnownZero, KnownOne, Depth+1);
1865 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1867 // If the sign bit of the input is known set or clear, then we know the
1868 // top bits of the result.
1869 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1870 KnownZero |= NewBits;
1871 KnownOne &= ~NewBits;
1872 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1873 KnownOne |= NewBits;
1874 KnownZero &= ~NewBits;
1875 } else { // Input sign bit unknown
1876 KnownZero &= ~NewBits;
1877 KnownOne &= ~NewBits;
1882 case ISD::CTTZ_ZERO_UNDEF:
1884 case ISD::CTLZ_ZERO_UNDEF:
1886 unsigned LowBits = Log2_32(BitWidth)+1;
1887 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1888 KnownOne.clearAllBits();
1892 if (ISD::isZEXTLoad(Op.getNode())) {
1893 LoadSDNode *LD = cast<LoadSDNode>(Op);
1894 EVT VT = LD->getMemoryVT();
1895 unsigned MemBits = VT.getScalarType().getSizeInBits();
1896 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask;
1900 case ISD::ZERO_EXTEND: {
1901 EVT InVT = Op.getOperand(0).getValueType();
1902 unsigned InBits = InVT.getScalarType().getSizeInBits();
1903 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1904 APInt InMask = Mask.trunc(InBits);
1905 KnownZero = KnownZero.trunc(InBits);
1906 KnownOne = KnownOne.trunc(InBits);
1907 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1908 KnownZero = KnownZero.zext(BitWidth);
1909 KnownOne = KnownOne.zext(BitWidth);
1910 KnownZero |= NewBits;
1913 case ISD::SIGN_EXTEND: {
1914 EVT InVT = Op.getOperand(0).getValueType();
1915 unsigned InBits = InVT.getScalarType().getSizeInBits();
1916 APInt InSignBit = APInt::getSignBit(InBits);
1917 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1918 APInt InMask = Mask.trunc(InBits);
1920 // If any of the sign extended bits are demanded, we know that the sign
1921 // bit is demanded. Temporarily set this bit in the mask for our callee.
1922 if (NewBits.getBoolValue())
1923 InMask |= InSignBit;
1925 KnownZero = KnownZero.trunc(InBits);
1926 KnownOne = KnownOne.trunc(InBits);
1927 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1929 // Note if the sign bit is known to be zero or one.
1930 bool SignBitKnownZero = KnownZero.isNegative();
1931 bool SignBitKnownOne = KnownOne.isNegative();
1932 assert(!(SignBitKnownZero && SignBitKnownOne) &&
1933 "Sign bit can't be known to be both zero and one!");
1935 // If the sign bit wasn't actually demanded by our caller, we don't
1936 // want it set in the KnownZero and KnownOne result values. Reset the
1937 // mask and reapply it to the result values.
1938 InMask = Mask.trunc(InBits);
1939 KnownZero &= InMask;
1942 KnownZero = KnownZero.zext(BitWidth);
1943 KnownOne = KnownOne.zext(BitWidth);
1945 // If the sign bit is known zero or one, the top bits match.
1946 if (SignBitKnownZero)
1947 KnownZero |= NewBits;
1948 else if (SignBitKnownOne)
1949 KnownOne |= NewBits;
1952 case ISD::ANY_EXTEND: {
1953 EVT InVT = Op.getOperand(0).getValueType();
1954 unsigned InBits = InVT.getScalarType().getSizeInBits();
1955 APInt InMask = Mask.trunc(InBits);
1956 KnownZero = KnownZero.trunc(InBits);
1957 KnownOne = KnownOne.trunc(InBits);
1958 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1959 KnownZero = KnownZero.zext(BitWidth);
1960 KnownOne = KnownOne.zext(BitWidth);
1963 case ISD::TRUNCATE: {
1964 EVT InVT = Op.getOperand(0).getValueType();
1965 unsigned InBits = InVT.getScalarType().getSizeInBits();
1966 APInt InMask = Mask.zext(InBits);
1967 KnownZero = KnownZero.zext(InBits);
1968 KnownOne = KnownOne.zext(InBits);
1969 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1970 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1971 KnownZero = KnownZero.trunc(BitWidth);
1972 KnownOne = KnownOne.trunc(BitWidth);
1975 case ISD::AssertZext: {
1976 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1977 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
1978 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
1980 KnownZero |= (~InMask) & Mask;
1984 // All bits are zero except the low bit.
1985 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1989 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1990 // We know that the top bits of C-X are clear if X contains less bits
1991 // than C (i.e. no wrap-around can happen). For example, 20-X is
1992 // positive if we can prove that X is >= 0 and < 16.
1993 if (CLHS->getAPIntValue().isNonNegative()) {
1994 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1995 // NLZ can't be BitWidth with no sign bit
1996 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1997 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2,
2000 // If all of the MaskV bits are known to be zero, then we know the
2001 // output top bits are zero, because we now know that the output is
2003 if ((KnownZero2 & MaskV) == MaskV) {
2004 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2005 // Top bits known zero.
2006 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
2014 // Output known-0 bits are known if clear or set in both the low clear bits
2015 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2016 // low 3 bits clear.
2017 APInt Mask2 = APInt::getLowBitsSet(BitWidth,
2018 BitWidth - Mask.countLeadingZeros());
2019 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
2020 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2021 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2023 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1);
2024 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2025 KnownZeroOut = std::min(KnownZeroOut,
2026 KnownZero2.countTrailingOnes());
2028 if (Op.getOpcode() == ISD::ADD) {
2029 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2033 // With ADDE, a carry bit may be added in, so we can only use this
2034 // information if we know (at least) that the low two bits are clear. We
2035 // then return to the caller that the low bit is unknown but that other bits
2037 if (KnownZeroOut >= 2) // ADDE
2038 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2042 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2043 const APInt &RA = Rem->getAPIntValue().abs();
2044 if (RA.isPowerOf2()) {
2045 APInt LowBits = RA - 1;
2046 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2047 ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1);
2049 // The low bits of the first operand are unchanged by the srem.
2050 KnownZero = KnownZero2 & LowBits;
2051 KnownOne = KnownOne2 & LowBits;
2053 // If the first operand is non-negative or has all low bits zero, then
2054 // the upper bits are all zero.
2055 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2056 KnownZero |= ~LowBits;
2058 // If the first operand is negative and not all low bits are zero, then
2059 // the upper bits are all one.
2060 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2061 KnownOne |= ~LowBits;
2066 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2071 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2072 const APInt &RA = Rem->getAPIntValue();
2073 if (RA.isPowerOf2()) {
2074 APInt LowBits = (RA - 1);
2075 APInt Mask2 = LowBits & Mask;
2076 KnownZero |= ~LowBits & Mask;
2077 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1);
2078 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2083 // Since the result is less than or equal to either operand, any leading
2084 // zero bits in either operand must also exist in the result.
2085 APInt AllOnes = APInt::getAllOnesValue(BitWidth);
2086 ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne,
2088 ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2,
2091 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2092 KnownZero2.countLeadingOnes());
2093 KnownOne.clearAllBits();
2094 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
2097 case ISD::FrameIndex:
2098 case ISD::TargetFrameIndex:
2099 if (unsigned Align = InferPtrAlignment(Op)) {
2100 // The low bits are known zero if the pointer is aligned.
2101 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2107 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2110 case ISD::INTRINSIC_WO_CHAIN:
2111 case ISD::INTRINSIC_W_CHAIN:
2112 case ISD::INTRINSIC_VOID:
2113 // Allow the target to implement this method for its nodes.
2114 TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this,
2120 /// ComputeNumSignBits - Return the number of times the sign bit of the
2121 /// register is replicated into the other bits. We know that at least 1 bit
2122 /// is always equal to the sign bit (itself), but other cases can give us
2123 /// information. For example, immediately after an "SRA X, 2", we know that
2124 /// the top 3 bits are all equal to each other, so we return 3.
2125 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2126 EVT VT = Op.getValueType();
2127 assert(VT.isInteger() && "Invalid VT!");
2128 unsigned VTBits = VT.getScalarType().getSizeInBits();
2130 unsigned FirstAnswer = 1;
2133 return 1; // Limit search depth.
2135 switch (Op.getOpcode()) {
2137 case ISD::AssertSext:
2138 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2139 return VTBits-Tmp+1;
2140 case ISD::AssertZext:
2141 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2144 case ISD::Constant: {
2145 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2146 return Val.getNumSignBits();
2149 case ISD::SIGN_EXTEND:
2150 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2151 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2153 case ISD::SIGN_EXTEND_INREG:
2154 // Max of the input and what this extends.
2156 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2159 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2160 return std::max(Tmp, Tmp2);
2163 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2164 // SRA X, C -> adds C sign bits.
2165 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2166 Tmp += C->getZExtValue();
2167 if (Tmp > VTBits) Tmp = VTBits;
2171 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2172 // shl destroys sign bits.
2173 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2174 if (C->getZExtValue() >= VTBits || // Bad shift.
2175 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2176 return Tmp - C->getZExtValue();
2181 case ISD::XOR: // NOT is handled here.
2182 // Logical binary ops preserve the number of sign bits at the worst.
2183 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2185 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2186 FirstAnswer = std::min(Tmp, Tmp2);
2187 // We computed what we know about the sign bits as our first
2188 // answer. Now proceed to the generic code that uses
2189 // ComputeMaskedBits, and pick whichever answer is better.
2194 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2195 if (Tmp == 1) return 1; // Early out.
2196 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2197 return std::min(Tmp, Tmp2);
2205 if (Op.getResNo() != 1)
2207 // The boolean result conforms to getBooleanContents. Fall through.
2209 // If setcc returns 0/-1, all bits are sign bits.
2210 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2211 TargetLowering::ZeroOrNegativeOneBooleanContent)
2216 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2217 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2219 // Handle rotate right by N like a rotate left by 32-N.
2220 if (Op.getOpcode() == ISD::ROTR)
2221 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2223 // If we aren't rotating out all of the known-in sign bits, return the
2224 // number that are left. This handles rotl(sext(x), 1) for example.
2225 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2226 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2230 // Add can have at most one carry bit. Thus we know that the output
2231 // is, at worst, one more bit than the inputs.
2232 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2233 if (Tmp == 1) return 1; // Early out.
2235 // Special case decrementing a value (ADD X, -1):
2236 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2237 if (CRHS->isAllOnesValue()) {
2238 APInt KnownZero, KnownOne;
2239 APInt Mask = APInt::getAllOnesValue(VTBits);
2240 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
2242 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2244 if ((KnownZero | APInt(VTBits, 1)) == Mask)
2247 // If we are subtracting one from a positive number, there is no carry
2248 // out of the result.
2249 if (KnownZero.isNegative())
2253 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2254 if (Tmp2 == 1) return 1;
2255 return std::min(Tmp, Tmp2)-1;
2258 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2259 if (Tmp2 == 1) return 1;
2262 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2263 if (CLHS->isNullValue()) {
2264 APInt KnownZero, KnownOne;
2265 APInt Mask = APInt::getAllOnesValue(VTBits);
2266 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
2267 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2269 if ((KnownZero | APInt(VTBits, 1)) == Mask)
2272 // If the input is known to be positive (the sign bit is known clear),
2273 // the output of the NEG has the same number of sign bits as the input.
2274 if (KnownZero.isNegative())
2277 // Otherwise, we treat this like a SUB.
2280 // Sub can have at most one carry bit. Thus we know that the output
2281 // is, at worst, one more bit than the inputs.
2282 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2283 if (Tmp == 1) return 1; // Early out.
2284 return std::min(Tmp, Tmp2)-1;
2286 // FIXME: it's tricky to do anything useful for this, but it is an important
2287 // case for targets like X86.
2291 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2292 if (Op.getOpcode() == ISD::LOAD) {
2293 LoadSDNode *LD = cast<LoadSDNode>(Op);
2294 unsigned ExtType = LD->getExtensionType();
2297 case ISD::SEXTLOAD: // '17' bits known
2298 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2299 return VTBits-Tmp+1;
2300 case ISD::ZEXTLOAD: // '16' bits known
2301 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2306 // Allow the target to implement this method for its nodes.
2307 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2308 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2309 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2310 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2311 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2312 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2315 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2316 // use this information.
2317 APInt KnownZero, KnownOne;
2318 APInt Mask = APInt::getAllOnesValue(VTBits);
2319 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
2321 if (KnownZero.isNegative()) { // sign bit is 0
2323 } else if (KnownOne.isNegative()) { // sign bit is 1;
2330 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2331 // the number of identical bits in the top of the input value.
2333 Mask <<= Mask.getBitWidth()-VTBits;
2334 // Return # leading zeros. We use 'min' here in case Val was zero before
2335 // shifting. We don't want to return '64' as for an i32 "0".
2336 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2339 /// isBaseWithConstantOffset - Return true if the specified operand is an
2340 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2341 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2342 /// semantics as an ADD. This handles the equivalence:
2343 /// X|Cst == X+Cst iff X&Cst = 0.
2344 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2345 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2346 !isa<ConstantSDNode>(Op.getOperand(1)))
2349 if (Op.getOpcode() == ISD::OR &&
2350 !MaskedValueIsZero(Op.getOperand(0),
2351 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2358 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2359 // If we're told that NaNs won't happen, assume they won't.
2360 if (getTarget().Options.NoNaNsFPMath)
2363 // If the value is a constant, we can obviously see if it is a NaN or not.
2364 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2365 return !C->getValueAPF().isNaN();
2367 // TODO: Recognize more cases here.
2372 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2373 // If the value is a constant, we can obviously see if it is a zero or not.
2374 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2375 return !C->isZero();
2377 // TODO: Recognize more cases here.
2378 switch (Op.getOpcode()) {
2381 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2382 return !C->isNullValue();
2389 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2390 // Check the obvious case.
2391 if (A == B) return true;
2393 // For for negative and positive zero.
2394 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2395 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2396 if (CA->isZero() && CB->isZero()) return true;
2398 // Otherwise they may not be equal.
2402 /// getNode - Gets or creates the specified node.
2404 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2405 FoldingSetNodeID ID;
2406 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2408 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2409 return SDValue(E, 0);
2411 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2412 CSEMap.InsertNode(N, IP);
2414 AllNodes.push_back(N);
2418 return SDValue(N, 0);
2421 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2422 EVT VT, SDValue Operand) {
2423 // Constant fold unary operations with an integer constant operand.
2424 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2425 const APInt &Val = C->getAPIntValue();
2428 case ISD::SIGN_EXTEND:
2429 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2430 case ISD::ANY_EXTEND:
2431 case ISD::ZERO_EXTEND:
2433 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2434 case ISD::UINT_TO_FP:
2435 case ISD::SINT_TO_FP: {
2436 // No compile time operations on ppcf128.
2437 if (VT == MVT::ppcf128) break;
2438 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2439 (void)apf.convertFromAPInt(Val,
2440 Opcode==ISD::SINT_TO_FP,
2441 APFloat::rmNearestTiesToEven);
2442 return getConstantFP(apf, VT);
2445 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2446 return getConstantFP(Val.bitsToFloat(), VT);
2447 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2448 return getConstantFP(Val.bitsToDouble(), VT);
2451 return getConstant(Val.byteSwap(), VT);
2453 return getConstant(Val.countPopulation(), VT);
2455 case ISD::CTLZ_ZERO_UNDEF:
2456 return getConstant(Val.countLeadingZeros(), VT);
2458 case ISD::CTTZ_ZERO_UNDEF:
2459 return getConstant(Val.countTrailingZeros(), VT);
2463 // Constant fold unary operations with a floating point constant operand.
2464 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2465 APFloat V = C->getValueAPF(); // make copy
2466 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2470 return getConstantFP(V, VT);
2473 return getConstantFP(V, VT);
2475 case ISD::FP_EXTEND: {
2477 // This can return overflow, underflow, or inexact; we don't care.
2478 // FIXME need to be more flexible about rounding mode.
2479 (void)V.convert(*EVTToAPFloatSemantics(VT),
2480 APFloat::rmNearestTiesToEven, &ignored);
2481 return getConstantFP(V, VT);
2483 case ISD::FP_TO_SINT:
2484 case ISD::FP_TO_UINT: {
2487 assert(integerPartWidth >= 64);
2488 // FIXME need to be more flexible about rounding mode.
2489 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2490 Opcode==ISD::FP_TO_SINT,
2491 APFloat::rmTowardZero, &ignored);
2492 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2494 APInt api(VT.getSizeInBits(), x);
2495 return getConstant(api, VT);
2498 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2499 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2500 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2501 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2507 unsigned OpOpcode = Operand.getNode()->getOpcode();
2509 case ISD::TokenFactor:
2510 case ISD::MERGE_VALUES:
2511 case ISD::CONCAT_VECTORS:
2512 return Operand; // Factor, merge or concat of one node? No need.
2513 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2514 case ISD::FP_EXTEND:
2515 assert(VT.isFloatingPoint() &&
2516 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2517 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2518 assert((!VT.isVector() ||
2519 VT.getVectorNumElements() ==
2520 Operand.getValueType().getVectorNumElements()) &&
2521 "Vector element count mismatch!");
2522 if (Operand.getOpcode() == ISD::UNDEF)
2523 return getUNDEF(VT);
2525 case ISD::SIGN_EXTEND:
2526 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2527 "Invalid SIGN_EXTEND!");
2528 if (Operand.getValueType() == VT) return Operand; // noop extension
2529 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2530 "Invalid sext node, dst < src!");
2531 assert((!VT.isVector() ||
2532 VT.getVectorNumElements() ==
2533 Operand.getValueType().getVectorNumElements()) &&
2534 "Vector element count mismatch!");
2535 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2536 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2537 else if (OpOpcode == ISD::UNDEF)
2538 // sext(undef) = 0, because the top bits will all be the same.
2539 return getConstant(0, VT);
2541 case ISD::ZERO_EXTEND:
2542 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2543 "Invalid ZERO_EXTEND!");
2544 if (Operand.getValueType() == VT) return Operand; // noop extension
2545 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2546 "Invalid zext node, dst < src!");
2547 assert((!VT.isVector() ||
2548 VT.getVectorNumElements() ==
2549 Operand.getValueType().getVectorNumElements()) &&
2550 "Vector element count mismatch!");
2551 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2552 return getNode(ISD::ZERO_EXTEND, DL, VT,
2553 Operand.getNode()->getOperand(0));
2554 else if (OpOpcode == ISD::UNDEF)
2555 // zext(undef) = 0, because the top bits will be zero.
2556 return getConstant(0, VT);
2558 case ISD::ANY_EXTEND:
2559 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2560 "Invalid ANY_EXTEND!");
2561 if (Operand.getValueType() == VT) return Operand; // noop extension
2562 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2563 "Invalid anyext node, dst < src!");
2564 assert((!VT.isVector() ||
2565 VT.getVectorNumElements() ==
2566 Operand.getValueType().getVectorNumElements()) &&
2567 "Vector element count mismatch!");
2569 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2570 OpOpcode == ISD::ANY_EXTEND)
2571 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2572 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2573 else if (OpOpcode == ISD::UNDEF)
2574 return getUNDEF(VT);
2576 // (ext (trunx x)) -> x
2577 if (OpOpcode == ISD::TRUNCATE) {
2578 SDValue OpOp = Operand.getNode()->getOperand(0);
2579 if (OpOp.getValueType() == VT)
2584 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2585 "Invalid TRUNCATE!");
2586 if (Operand.getValueType() == VT) return Operand; // noop truncate
2587 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2588 "Invalid truncate node, src < dst!");
2589 assert((!VT.isVector() ||
2590 VT.getVectorNumElements() ==
2591 Operand.getValueType().getVectorNumElements()) &&
2592 "Vector element count mismatch!");
2593 if (OpOpcode == ISD::TRUNCATE)
2594 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2595 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2596 OpOpcode == ISD::ANY_EXTEND) {
2597 // If the source is smaller than the dest, we still need an extend.
2598 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2599 .bitsLT(VT.getScalarType()))
2600 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2601 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2602 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2603 return Operand.getNode()->getOperand(0);
2605 if (OpOpcode == ISD::UNDEF)
2606 return getUNDEF(VT);
2609 // Basic sanity checking.
2610 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2611 && "Cannot BITCAST between types of different sizes!");
2612 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2613 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2614 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2615 if (OpOpcode == ISD::UNDEF)
2616 return getUNDEF(VT);
2618 case ISD::SCALAR_TO_VECTOR:
2619 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2620 (VT.getVectorElementType() == Operand.getValueType() ||
2621 (VT.getVectorElementType().isInteger() &&
2622 Operand.getValueType().isInteger() &&
2623 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2624 "Illegal SCALAR_TO_VECTOR node!");
2625 if (OpOpcode == ISD::UNDEF)
2626 return getUNDEF(VT);
2627 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2628 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2629 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2630 Operand.getConstantOperandVal(1) == 0 &&
2631 Operand.getOperand(0).getValueType() == VT)
2632 return Operand.getOperand(0);
2635 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2636 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2637 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2638 Operand.getNode()->getOperand(0));
2639 if (OpOpcode == ISD::FNEG) // --X -> X
2640 return Operand.getNode()->getOperand(0);
2643 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2644 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2649 SDVTList VTs = getVTList(VT);
2650 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2651 FoldingSetNodeID ID;
2652 SDValue Ops[1] = { Operand };
2653 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2655 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2656 return SDValue(E, 0);
2658 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2659 CSEMap.InsertNode(N, IP);
2661 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2664 AllNodes.push_back(N);
2668 return SDValue(N, 0);
2671 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2673 ConstantSDNode *Cst1,
2674 ConstantSDNode *Cst2) {
2675 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2678 case ISD::ADD: return getConstant(C1 + C2, VT);
2679 case ISD::SUB: return getConstant(C1 - C2, VT);
2680 case ISD::MUL: return getConstant(C1 * C2, VT);
2682 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2685 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2688 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2691 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2693 case ISD::AND: return getConstant(C1 & C2, VT);
2694 case ISD::OR: return getConstant(C1 | C2, VT);
2695 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2696 case ISD::SHL: return getConstant(C1 << C2, VT);
2697 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2698 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2699 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2700 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2707 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2708 SDValue N1, SDValue N2) {
2709 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2710 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2713 case ISD::TokenFactor:
2714 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2715 N2.getValueType() == MVT::Other && "Invalid token factor!");
2716 // Fold trivial token factors.
2717 if (N1.getOpcode() == ISD::EntryToken) return N2;
2718 if (N2.getOpcode() == ISD::EntryToken) return N1;
2719 if (N1 == N2) return N1;
2721 case ISD::CONCAT_VECTORS:
2722 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2723 // one big BUILD_VECTOR.
2724 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2725 N2.getOpcode() == ISD::BUILD_VECTOR) {
2726 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2727 N1.getNode()->op_end());
2728 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2729 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2733 assert(VT.isInteger() && "This operator does not apply to FP types!");
2734 assert(N1.getValueType() == N2.getValueType() &&
2735 N1.getValueType() == VT && "Binary operator types must match!");
2736 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2737 // worth handling here.
2738 if (N2C && N2C->isNullValue())
2740 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2747 assert(VT.isInteger() && "This operator does not apply to FP types!");
2748 assert(N1.getValueType() == N2.getValueType() &&
2749 N1.getValueType() == VT && "Binary operator types must match!");
2750 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2751 // it's worth handling here.
2752 if (N2C && N2C->isNullValue())
2762 assert(VT.isInteger() && "This operator does not apply to FP types!");
2763 assert(N1.getValueType() == N2.getValueType() &&
2764 N1.getValueType() == VT && "Binary operator types must match!");
2771 if (getTarget().Options.UnsafeFPMath) {
2772 if (Opcode == ISD::FADD) {
2774 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2775 if (CFP->getValueAPF().isZero())
2778 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2779 if (CFP->getValueAPF().isZero())
2781 } else if (Opcode == ISD::FSUB) {
2783 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2784 if (CFP->getValueAPF().isZero())
2788 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2789 assert(N1.getValueType() == N2.getValueType() &&
2790 N1.getValueType() == VT && "Binary operator types must match!");
2792 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2793 assert(N1.getValueType() == VT &&
2794 N1.getValueType().isFloatingPoint() &&
2795 N2.getValueType().isFloatingPoint() &&
2796 "Invalid FCOPYSIGN!");
2803 assert(VT == N1.getValueType() &&
2804 "Shift operators return type must be the same as their first arg");
2805 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2806 "Shifts only work on integers");
2807 // Verify that the shift amount VT is bit enough to hold valid shift
2808 // amounts. This catches things like trying to shift an i1024 value by an
2809 // i8, which is easy to fall into in generic code that uses
2810 // TLI.getShiftAmount().
2811 assert(N2.getValueType().getSizeInBits() >=
2812 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2813 "Invalid use of small shift amount with oversized value!");
2815 // Always fold shifts of i1 values so the code generator doesn't need to
2816 // handle them. Since we know the size of the shift has to be less than the
2817 // size of the value, the shift/rotate count is guaranteed to be zero.
2820 if (N2C && N2C->isNullValue())
2823 case ISD::FP_ROUND_INREG: {
2824 EVT EVT = cast<VTSDNode>(N2)->getVT();
2825 assert(VT == N1.getValueType() && "Not an inreg round!");
2826 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2827 "Cannot FP_ROUND_INREG integer types");
2828 assert(EVT.isVector() == VT.isVector() &&
2829 "FP_ROUND_INREG type should be vector iff the operand "
2831 assert((!EVT.isVector() ||
2832 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2833 "Vector element counts must match in FP_ROUND_INREG");
2834 assert(EVT.bitsLE(VT) && "Not rounding down!");
2836 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2840 assert(VT.isFloatingPoint() &&
2841 N1.getValueType().isFloatingPoint() &&
2842 VT.bitsLE(N1.getValueType()) &&
2843 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2844 if (N1.getValueType() == VT) return N1; // noop conversion.
2846 case ISD::AssertSext:
2847 case ISD::AssertZext: {
2848 EVT EVT = cast<VTSDNode>(N2)->getVT();
2849 assert(VT == N1.getValueType() && "Not an inreg extend!");
2850 assert(VT.isInteger() && EVT.isInteger() &&
2851 "Cannot *_EXTEND_INREG FP types");
2852 assert(!EVT.isVector() &&
2853 "AssertSExt/AssertZExt type should be the vector element type "
2854 "rather than the vector type!");
2855 assert(EVT.bitsLE(VT) && "Not extending!");
2856 if (VT == EVT) return N1; // noop assertion.
2859 case ISD::SIGN_EXTEND_INREG: {
2860 EVT EVT = cast<VTSDNode>(N2)->getVT();
2861 assert(VT == N1.getValueType() && "Not an inreg extend!");
2862 assert(VT.isInteger() && EVT.isInteger() &&
2863 "Cannot *_EXTEND_INREG FP types");
2864 assert(EVT.isVector() == VT.isVector() &&
2865 "SIGN_EXTEND_INREG type should be vector iff the operand "
2867 assert((!EVT.isVector() ||
2868 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2869 "Vector element counts must match in SIGN_EXTEND_INREG");
2870 assert(EVT.bitsLE(VT) && "Not extending!");
2871 if (EVT == VT) return N1; // Not actually extending
2874 APInt Val = N1C->getAPIntValue();
2875 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2876 Val <<= Val.getBitWidth()-FromBits;
2877 Val = Val.ashr(Val.getBitWidth()-FromBits);
2878 return getConstant(Val, VT);
2882 case ISD::EXTRACT_VECTOR_ELT:
2883 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2884 if (N1.getOpcode() == ISD::UNDEF)
2885 return getUNDEF(VT);
2887 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2888 // expanding copies of large vectors from registers.
2890 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2891 N1.getNumOperands() > 0) {
2893 N1.getOperand(0).getValueType().getVectorNumElements();
2894 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2895 N1.getOperand(N2C->getZExtValue() / Factor),
2896 getConstant(N2C->getZExtValue() % Factor,
2897 N2.getValueType()));
2900 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2901 // expanding large vector constants.
2902 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2903 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2904 EVT VEltTy = N1.getValueType().getVectorElementType();
2905 if (Elt.getValueType() != VEltTy) {
2906 // If the vector element type is not legal, the BUILD_VECTOR operands
2907 // are promoted and implicitly truncated. Make that explicit here.
2908 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt);
2911 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT
2912 // result is implicitly extended.
2913 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt);
2918 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2919 // operations are lowered to scalars.
2920 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2921 // If the indices are the same, return the inserted element else
2922 // if the indices are known different, extract the element from
2923 // the original vector.
2924 SDValue N1Op2 = N1.getOperand(2);
2925 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2927 if (N1Op2C && N2C) {
2928 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2929 if (VT == N1.getOperand(1).getValueType())
2930 return N1.getOperand(1);
2932 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2935 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2939 case ISD::EXTRACT_ELEMENT:
2940 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2941 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2942 (N1.getValueType().isInteger() == VT.isInteger()) &&
2943 N1.getValueType() != VT &&
2944 "Wrong types for EXTRACT_ELEMENT!");
2946 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2947 // 64-bit integers into 32-bit parts. Instead of building the extract of
2948 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2949 if (N1.getOpcode() == ISD::BUILD_PAIR)
2950 return N1.getOperand(N2C->getZExtValue());
2952 // EXTRACT_ELEMENT of a constant int is also very common.
2953 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2954 unsigned ElementSize = VT.getSizeInBits();
2955 unsigned Shift = ElementSize * N2C->getZExtValue();
2956 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2957 return getConstant(ShiftedVal.trunc(ElementSize), VT);
2960 case ISD::EXTRACT_SUBVECTOR: {
2962 if (VT.isSimple() && N1.getValueType().isSimple()) {
2963 assert(VT.isVector() && N1.getValueType().isVector() &&
2964 "Extract subvector VTs must be a vectors!");
2965 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
2966 "Extract subvector VTs must have the same element type!");
2967 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
2968 "Extract subvector must be from larger vector to smaller vector!");
2970 if (isa<ConstantSDNode>(Index.getNode())) {
2971 assert((VT.getVectorNumElements() +
2972 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
2973 <= N1.getValueType().getVectorNumElements())
2974 && "Extract subvector overflow!");
2977 // Trivial extraction.
2978 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
2987 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
2988 if (SV.getNode()) return SV;
2989 } else { // Cannonicalize constant to RHS if commutative
2990 if (isCommutativeBinOp(Opcode)) {
2991 std::swap(N1C, N2C);
2997 // Constant fold FP operations.
2998 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
2999 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3001 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3002 // Cannonicalize constant to RHS if commutative
3003 std::swap(N1CFP, N2CFP);
3005 } else if (N2CFP && VT != MVT::ppcf128) {
3006 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3007 APFloat::opStatus s;
3010 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3011 if (s != APFloat::opInvalidOp)
3012 return getConstantFP(V1, VT);
3015 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3016 if (s!=APFloat::opInvalidOp)
3017 return getConstantFP(V1, VT);
3020 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3021 if (s!=APFloat::opInvalidOp)
3022 return getConstantFP(V1, VT);
3025 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3026 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3027 return getConstantFP(V1, VT);
3030 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3031 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3032 return getConstantFP(V1, VT);
3034 case ISD::FCOPYSIGN:
3036 return getConstantFP(V1, VT);
3042 // Canonicalize an UNDEF to the RHS, even over a constant.
3043 if (N1.getOpcode() == ISD::UNDEF) {
3044 if (isCommutativeBinOp(Opcode)) {
3048 case ISD::FP_ROUND_INREG:
3049 case ISD::SIGN_EXTEND_INREG:
3055 return N1; // fold op(undef, arg2) -> undef
3063 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3064 // For vectors, we can't easily build an all zero vector, just return
3071 // Fold a bunch of operators when the RHS is undef.
3072 if (N2.getOpcode() == ISD::UNDEF) {
3075 if (N1.getOpcode() == ISD::UNDEF)
3076 // Handle undef ^ undef -> 0 special case. This is a common
3078 return getConstant(0, VT);
3088 return N2; // fold op(arg1, undef) -> undef
3094 if (getTarget().Options.UnsafeFPMath)
3102 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3103 // For vectors, we can't easily build an all zero vector, just return
3108 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3109 // For vectors, we can't easily build an all one vector, just return
3117 // Memoize this node if possible.
3119 SDVTList VTs = getVTList(VT);
3120 if (VT != MVT::Glue) {
3121 SDValue Ops[] = { N1, N2 };
3122 FoldingSetNodeID ID;
3123 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3125 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3126 return SDValue(E, 0);
3128 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3129 CSEMap.InsertNode(N, IP);
3131 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3134 AllNodes.push_back(N);
3138 return SDValue(N, 0);
3141 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3142 SDValue N1, SDValue N2, SDValue N3) {
3143 // Perform various simplifications.
3144 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3146 case ISD::CONCAT_VECTORS:
3147 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3148 // one big BUILD_VECTOR.
3149 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3150 N2.getOpcode() == ISD::BUILD_VECTOR &&
3151 N3.getOpcode() == ISD::BUILD_VECTOR) {
3152 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3153 N1.getNode()->op_end());
3154 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3155 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3156 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3160 // Use FoldSetCC to simplify SETCC's.
3161 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3162 if (Simp.getNode()) return Simp;
3167 if (N1C->getZExtValue())
3168 return N2; // select true, X, Y -> X
3169 return N3; // select false, X, Y -> Y
3172 if (N2 == N3) return N2; // select C, X, X -> X
3174 case ISD::VECTOR_SHUFFLE:
3175 llvm_unreachable("should use getVectorShuffle constructor!");
3176 case ISD::INSERT_SUBVECTOR: {
3178 if (VT.isSimple() && N1.getValueType().isSimple()
3179 && N2.getValueType().isSimple()) {
3180 assert(VT.isVector() && N1.getValueType().isVector() &&
3181 N2.getValueType().isVector() &&
3182 "Insert subvector VTs must be a vectors");
3183 assert(VT == N1.getValueType() &&
3184 "Dest and insert subvector source types must match!");
3185 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3186 "Insert subvector must be from smaller vector to larger vector!");
3187 if (isa<ConstantSDNode>(Index.getNode())) {
3188 assert((N2.getValueType().getVectorNumElements() +
3189 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3190 <= VT.getVectorNumElements())
3191 && "Insert subvector overflow!");
3194 // Trivial insertion.
3195 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3201 // Fold bit_convert nodes from a type to themselves.
3202 if (N1.getValueType() == VT)
3207 // Memoize node if it doesn't produce a flag.
3209 SDVTList VTs = getVTList(VT);
3210 if (VT != MVT::Glue) {
3211 SDValue Ops[] = { N1, N2, N3 };
3212 FoldingSetNodeID ID;
3213 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3215 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3216 return SDValue(E, 0);
3218 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3219 CSEMap.InsertNode(N, IP);
3221 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3224 AllNodes.push_back(N);
3228 return SDValue(N, 0);
3231 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3232 SDValue N1, SDValue N2, SDValue N3,
3234 SDValue Ops[] = { N1, N2, N3, N4 };
3235 return getNode(Opcode, DL, VT, Ops, 4);
3238 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3239 SDValue N1, SDValue N2, SDValue N3,
3240 SDValue N4, SDValue N5) {
3241 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3242 return getNode(Opcode, DL, VT, Ops, 5);
3245 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3246 /// the incoming stack arguments to be loaded from the stack.
3247 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3248 SmallVector<SDValue, 8> ArgChains;
3250 // Include the original chain at the beginning of the list. When this is
3251 // used by target LowerCall hooks, this helps legalize find the
3252 // CALLSEQ_BEGIN node.
3253 ArgChains.push_back(Chain);
3255 // Add a chain value for each stack argument.
3256 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3257 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3258 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3259 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3260 if (FI->getIndex() < 0)
3261 ArgChains.push_back(SDValue(L, 1));
3263 // Build a tokenfactor for all the chains.
3264 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3265 &ArgChains[0], ArgChains.size());
3268 /// SplatByte - Distribute ByteVal over NumBits bits.
3269 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3270 APInt Val = APInt(NumBits, ByteVal);
3272 for (unsigned i = NumBits; i > 8; i >>= 1) {
3273 Val = (Val << Shift) | Val;
3279 /// getMemsetValue - Vectorized representation of the memset value
3281 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3283 assert(Value.getOpcode() != ISD::UNDEF);
3285 unsigned NumBits = VT.getScalarType().getSizeInBits();
3286 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3287 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3289 return DAG.getConstant(Val, VT);
3290 return DAG.getConstantFP(APFloat(Val), VT);
3293 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3295 // Use a multiplication with 0x010101... to extend the input to the
3297 APInt Magic = SplatByte(NumBits, 0x01);
3298 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3304 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3305 /// used when a memcpy is turned into a memset when the source is a constant
3307 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3308 const TargetLowering &TLI, StringRef Str) {
3309 // Handle vector with all elements zero.
3312 return DAG.getConstant(0, VT);
3313 else if (VT == MVT::f32 || VT == MVT::f64)
3314 return DAG.getConstantFP(0.0, VT);
3315 else if (VT.isVector()) {
3316 unsigned NumElts = VT.getVectorNumElements();
3317 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3318 return DAG.getNode(ISD::BITCAST, dl, VT,
3319 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3322 llvm_unreachable("Expected type!");
3325 assert(!VT.isVector() && "Can't handle vector type here!");
3326 unsigned NumVTBytes = VT.getSizeInBits() / 8;
3327 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3330 if (TLI.isLittleEndian()) {
3331 for (unsigned i = 0; i != NumBytes; ++i)
3332 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3334 for (unsigned i = 0; i != NumBytes; ++i)
3335 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3338 return DAG.getConstant(Val, VT);
3341 /// getMemBasePlusOffset - Returns base and offset node for the
3343 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3344 SelectionDAG &DAG) {
3345 EVT VT = Base.getValueType();
3346 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3347 VT, Base, DAG.getConstant(Offset, VT));
3350 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3352 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3353 unsigned SrcDelta = 0;
3354 GlobalAddressSDNode *G = NULL;
3355 if (Src.getOpcode() == ISD::GlobalAddress)
3356 G = cast<GlobalAddressSDNode>(Src);
3357 else if (Src.getOpcode() == ISD::ADD &&
3358 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3359 Src.getOperand(1).getOpcode() == ISD::Constant) {
3360 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3361 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3366 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3369 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3370 /// to replace the memset / memcpy. Return true if the number of memory ops
3371 /// is below the threshold. It returns the types of the sequence of
3372 /// memory ops to perform memset / memcpy by reference.
3373 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3374 unsigned Limit, uint64_t Size,
3375 unsigned DstAlign, unsigned SrcAlign,
3379 const TargetLowering &TLI) {
3380 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3381 "Expecting memcpy / memset source to meet alignment requirement!");
3382 // If 'SrcAlign' is zero, that means the memory operation does not need to
3383 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3384 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3385 // is the specified alignment of the memory operation. If it is zero, that
3386 // means it's possible to change the alignment of the destination.
3387 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3388 // not need to be loaded.
3389 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3390 IsZeroVal, MemcpyStrSrc,
3391 DAG.getMachineFunction());
3393 if (VT == MVT::Other) {
3394 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3395 TLI.allowsUnalignedMemoryAccesses(VT)) {
3396 VT = TLI.getPointerTy();
3398 switch (DstAlign & 7) {
3399 case 0: VT = MVT::i64; break;
3400 case 4: VT = MVT::i32; break;
3401 case 2: VT = MVT::i16; break;
3402 default: VT = MVT::i8; break;
3407 while (!TLI.isTypeLegal(LVT))
3408 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3409 assert(LVT.isInteger());
3415 unsigned NumMemOps = 0;
3417 unsigned VTSize = VT.getSizeInBits() / 8;
3418 while (VTSize > Size) {
3419 // For now, only use non-vector load / store's for the left-over pieces.
3420 if (VT.isVector() || VT.isFloatingPoint()) {
3422 while (!TLI.isTypeLegal(VT))
3423 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3424 VTSize = VT.getSizeInBits() / 8;
3426 // This can result in a type that is not legal on the target, e.g.
3427 // 1 or 2 bytes on PPC.
3428 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3433 if (++NumMemOps > Limit)
3435 MemOps.push_back(VT);
3442 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3443 SDValue Chain, SDValue Dst,
3444 SDValue Src, uint64_t Size,
3445 unsigned Align, bool isVol,
3447 MachinePointerInfo DstPtrInfo,
3448 MachinePointerInfo SrcPtrInfo) {
3449 // Turn a memcpy of undef to nop.
3450 if (Src.getOpcode() == ISD::UNDEF)
3453 // Expand memcpy to a series of load and store ops if the size operand falls
3454 // below a certain threshold.
3455 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3456 // rather than maybe a humongous number of loads and stores.
3457 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3458 std::vector<EVT> MemOps;
3459 bool DstAlignCanChange = false;
3460 MachineFunction &MF = DAG.getMachineFunction();
3461 MachineFrameInfo *MFI = MF.getFrameInfo();
3462 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3463 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3464 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3465 DstAlignCanChange = true;
3466 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3467 if (Align > SrcAlign)
3470 bool CopyFromStr = isMemSrcFromString(Src, Str);
3471 bool isZeroStr = CopyFromStr && Str.empty();
3472 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3474 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3475 (DstAlignCanChange ? 0 : Align),
3476 (isZeroStr ? 0 : SrcAlign),
3477 true, CopyFromStr, DAG, TLI))
3480 if (DstAlignCanChange) {
3481 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3482 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3483 if (NewAlign > Align) {
3484 // Give the stack frame object a larger alignment if needed.
3485 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3486 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3491 SmallVector<SDValue, 8> OutChains;
3492 unsigned NumMemOps = MemOps.size();
3493 uint64_t SrcOff = 0, DstOff = 0;
3494 for (unsigned i = 0; i != NumMemOps; ++i) {
3496 unsigned VTSize = VT.getSizeInBits() / 8;
3497 SDValue Value, Store;
3500 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3501 // It's unlikely a store of a vector immediate can be done in a single
3502 // instruction. It would require a load from a constantpool first.
3503 // We only handle zero vectors here.
3504 // FIXME: Handle other cases where store of vector immediate is done in
3505 // a single instruction.
3506 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3507 Store = DAG.getStore(Chain, dl, Value,
3508 getMemBasePlusOffset(Dst, DstOff, DAG),
3509 DstPtrInfo.getWithOffset(DstOff), isVol,
3512 // The type might not be legal for the target. This should only happen
3513 // if the type is smaller than a legal type, as on PPC, so the right
3514 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3515 // to Load/Store if NVT==VT.
3516 // FIXME does the case above also need this?
3517 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3518 assert(NVT.bitsGE(VT));
3519 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3520 getMemBasePlusOffset(Src, SrcOff, DAG),
3521 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3522 MinAlign(SrcAlign, SrcOff));
3523 Store = DAG.getTruncStore(Chain, dl, Value,
3524 getMemBasePlusOffset(Dst, DstOff, DAG),
3525 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3528 OutChains.push_back(Store);
3533 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3534 &OutChains[0], OutChains.size());
3537 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3538 SDValue Chain, SDValue Dst,
3539 SDValue Src, uint64_t Size,
3540 unsigned Align, bool isVol,
3542 MachinePointerInfo DstPtrInfo,
3543 MachinePointerInfo SrcPtrInfo) {
3544 // Turn a memmove of undef to nop.
3545 if (Src.getOpcode() == ISD::UNDEF)
3548 // Expand memmove to a series of load and store ops if the size operand falls
3549 // below a certain threshold.
3550 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3551 std::vector<EVT> MemOps;
3552 bool DstAlignCanChange = false;
3553 MachineFunction &MF = DAG.getMachineFunction();
3554 MachineFrameInfo *MFI = MF.getFrameInfo();
3555 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3556 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3557 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3558 DstAlignCanChange = true;
3559 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3560 if (Align > SrcAlign)
3562 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3564 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3565 (DstAlignCanChange ? 0 : Align),
3566 SrcAlign, true, false, DAG, TLI))
3569 if (DstAlignCanChange) {
3570 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3571 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3572 if (NewAlign > Align) {
3573 // Give the stack frame object a larger alignment if needed.
3574 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3575 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3580 uint64_t SrcOff = 0, DstOff = 0;
3581 SmallVector<SDValue, 8> LoadValues;
3582 SmallVector<SDValue, 8> LoadChains;
3583 SmallVector<SDValue, 8> OutChains;
3584 unsigned NumMemOps = MemOps.size();
3585 for (unsigned i = 0; i < NumMemOps; i++) {
3587 unsigned VTSize = VT.getSizeInBits() / 8;
3588 SDValue Value, Store;
3590 Value = DAG.getLoad(VT, dl, Chain,
3591 getMemBasePlusOffset(Src, SrcOff, DAG),
3592 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3593 false, false, SrcAlign);
3594 LoadValues.push_back(Value);
3595 LoadChains.push_back(Value.getValue(1));
3598 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3599 &LoadChains[0], LoadChains.size());
3601 for (unsigned i = 0; i < NumMemOps; i++) {
3603 unsigned VTSize = VT.getSizeInBits() / 8;
3604 SDValue Value, Store;
3606 Store = DAG.getStore(Chain, dl, LoadValues[i],
3607 getMemBasePlusOffset(Dst, DstOff, DAG),
3608 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3609 OutChains.push_back(Store);
3613 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3614 &OutChains[0], OutChains.size());
3617 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3618 SDValue Chain, SDValue Dst,
3619 SDValue Src, uint64_t Size,
3620 unsigned Align, bool isVol,
3621 MachinePointerInfo DstPtrInfo) {
3622 // Turn a memset of undef to nop.
3623 if (Src.getOpcode() == ISD::UNDEF)
3626 // Expand memset to a series of load/store ops if the size operand
3627 // falls below a certain threshold.
3628 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3629 std::vector<EVT> MemOps;
3630 bool DstAlignCanChange = false;
3631 MachineFunction &MF = DAG.getMachineFunction();
3632 MachineFrameInfo *MFI = MF.getFrameInfo();
3633 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3634 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3635 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3636 DstAlignCanChange = true;
3638 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3639 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3640 Size, (DstAlignCanChange ? 0 : Align), 0,
3641 IsZeroVal, false, DAG, TLI))
3644 if (DstAlignCanChange) {
3645 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3646 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3647 if (NewAlign > Align) {
3648 // Give the stack frame object a larger alignment if needed.
3649 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3650 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3655 SmallVector<SDValue, 8> OutChains;
3656 uint64_t DstOff = 0;
3657 unsigned NumMemOps = MemOps.size();
3659 // Find the largest store and generate the bit pattern for it.
3660 EVT LargestVT = MemOps[0];
3661 for (unsigned i = 1; i < NumMemOps; i++)
3662 if (MemOps[i].bitsGT(LargestVT))
3663 LargestVT = MemOps[i];
3664 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3666 for (unsigned i = 0; i < NumMemOps; i++) {
3669 // If this store is smaller than the largest store see whether we can get
3670 // the smaller value for free with a truncate.
3671 SDValue Value = MemSetValue;
3672 if (VT.bitsLT(LargestVT)) {
3673 if (!LargestVT.isVector() && !VT.isVector() &&
3674 TLI.isTruncateFree(LargestVT, VT))
3675 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3677 Value = getMemsetValue(Src, VT, DAG, dl);
3679 assert(Value.getValueType() == VT && "Value with wrong type.");
3680 SDValue Store = DAG.getStore(Chain, dl, Value,
3681 getMemBasePlusOffset(Dst, DstOff, DAG),
3682 DstPtrInfo.getWithOffset(DstOff),
3683 isVol, false, Align);
3684 OutChains.push_back(Store);
3685 DstOff += VT.getSizeInBits() / 8;
3688 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3689 &OutChains[0], OutChains.size());
3692 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3693 SDValue Src, SDValue Size,
3694 unsigned Align, bool isVol, bool AlwaysInline,
3695 MachinePointerInfo DstPtrInfo,
3696 MachinePointerInfo SrcPtrInfo) {
3698 // Check to see if we should lower the memcpy to loads and stores first.
3699 // For cases within the target-specified limits, this is the best choice.
3700 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3702 // Memcpy with size zero? Just return the original chain.
3703 if (ConstantSize->isNullValue())
3706 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3707 ConstantSize->getZExtValue(),Align,
3708 isVol, false, DstPtrInfo, SrcPtrInfo);
3709 if (Result.getNode())
3713 // Then check to see if we should lower the memcpy with target-specific
3714 // code. If the target chooses to do this, this is the next best.
3716 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3717 isVol, AlwaysInline,
3718 DstPtrInfo, SrcPtrInfo);
3719 if (Result.getNode())
3722 // If we really need inline code and the target declined to provide it,
3723 // use a (potentially long) sequence of loads and stores.
3725 assert(ConstantSize && "AlwaysInline requires a constant size!");
3726 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3727 ConstantSize->getZExtValue(), Align, isVol,
3728 true, DstPtrInfo, SrcPtrInfo);
3731 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3732 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3733 // respect volatile, so they may do things like read or write memory
3734 // beyond the given memory regions. But fixing this isn't easy, and most
3735 // people don't care.
3737 // Emit a library call.
3738 TargetLowering::ArgListTy Args;
3739 TargetLowering::ArgListEntry Entry;
3740 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3741 Entry.Node = Dst; Args.push_back(Entry);
3742 Entry.Node = Src; Args.push_back(Entry);
3743 Entry.Node = Size; Args.push_back(Entry);
3744 // FIXME: pass in DebugLoc
3745 std::pair<SDValue,SDValue> CallResult =
3746 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()),
3747 false, false, false, false, 0,
3748 TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3749 /*isTailCall=*/false,
3750 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3751 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3752 TLI.getPointerTy()),
3754 return CallResult.second;
3757 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3758 SDValue Src, SDValue Size,
3759 unsigned Align, bool isVol,
3760 MachinePointerInfo DstPtrInfo,
3761 MachinePointerInfo SrcPtrInfo) {
3763 // Check to see if we should lower the memmove to loads and stores first.
3764 // For cases within the target-specified limits, this is the best choice.
3765 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3767 // Memmove with size zero? Just return the original chain.
3768 if (ConstantSize->isNullValue())
3772 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3773 ConstantSize->getZExtValue(), Align, isVol,
3774 false, DstPtrInfo, SrcPtrInfo);
3775 if (Result.getNode())
3779 // Then check to see if we should lower the memmove with target-specific
3780 // code. If the target chooses to do this, this is the next best.
3782 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3783 DstPtrInfo, SrcPtrInfo);
3784 if (Result.getNode())
3787 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3788 // not be safe. See memcpy above for more details.
3790 // Emit a library call.
3791 TargetLowering::ArgListTy Args;
3792 TargetLowering::ArgListEntry Entry;
3793 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3794 Entry.Node = Dst; Args.push_back(Entry);
3795 Entry.Node = Src; Args.push_back(Entry);
3796 Entry.Node = Size; Args.push_back(Entry);
3797 // FIXME: pass in DebugLoc
3798 std::pair<SDValue,SDValue> CallResult =
3799 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()),
3800 false, false, false, false, 0,
3801 TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3802 /*isTailCall=*/false,
3803 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3804 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3805 TLI.getPointerTy()),
3807 return CallResult.second;
3810 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3811 SDValue Src, SDValue Size,
3812 unsigned Align, bool isVol,
3813 MachinePointerInfo DstPtrInfo) {
3815 // Check to see if we should lower the memset to stores first.
3816 // For cases within the target-specified limits, this is the best choice.
3817 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3819 // Memset with size zero? Just return the original chain.
3820 if (ConstantSize->isNullValue())
3824 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3825 Align, isVol, DstPtrInfo);
3827 if (Result.getNode())
3831 // Then check to see if we should lower the memset with target-specific
3832 // code. If the target chooses to do this, this is the next best.
3834 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3836 if (Result.getNode())
3839 // Emit a library call.
3840 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3841 TargetLowering::ArgListTy Args;
3842 TargetLowering::ArgListEntry Entry;
3843 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3844 Args.push_back(Entry);
3845 // Extend or truncate the argument to be an i32 value for the call.
3846 if (Src.getValueType().bitsGT(MVT::i32))
3847 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3849 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3851 Entry.Ty = Type::getInt32Ty(*getContext());
3852 Entry.isSExt = true;
3853 Args.push_back(Entry);
3855 Entry.Ty = IntPtrTy;
3856 Entry.isSExt = false;
3857 Args.push_back(Entry);
3858 // FIXME: pass in DebugLoc
3859 std::pair<SDValue,SDValue> CallResult =
3860 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()),
3861 false, false, false, false, 0,
3862 TLI.getLibcallCallingConv(RTLIB::MEMSET),
3863 /*isTailCall=*/false,
3864 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3865 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3866 TLI.getPointerTy()),
3868 return CallResult.second;
3871 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3872 SDValue Chain, SDValue Ptr, SDValue Cmp,
3873 SDValue Swp, MachinePointerInfo PtrInfo,
3875 AtomicOrdering Ordering,
3876 SynchronizationScope SynchScope) {
3877 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3878 Alignment = getEVTAlignment(MemVT);
3880 MachineFunction &MF = getMachineFunction();
3881 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
3883 // For now, atomics are considered to be volatile always.
3884 // FIXME: Volatile isn't really correct; we should keep track of atomic
3885 // orderings in the memoperand.
3886 Flags |= MachineMemOperand::MOVolatile;
3888 MachineMemOperand *MMO =
3889 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3891 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3892 Ordering, SynchScope);
3895 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3897 SDValue Ptr, SDValue Cmp,
3898 SDValue Swp, MachineMemOperand *MMO,
3899 AtomicOrdering Ordering,
3900 SynchronizationScope SynchScope) {
3901 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3902 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3904 EVT VT = Cmp.getValueType();
3906 SDVTList VTs = getVTList(VT, MVT::Other);
3907 FoldingSetNodeID ID;
3908 ID.AddInteger(MemVT.getRawBits());
3909 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3910 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3912 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3913 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3914 return SDValue(E, 0);
3916 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3917 Ptr, Cmp, Swp, MMO, Ordering,
3919 CSEMap.InsertNode(N, IP);
3920 AllNodes.push_back(N);
3921 return SDValue(N, 0);
3924 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3926 SDValue Ptr, SDValue Val,
3927 const Value* PtrVal,
3929 AtomicOrdering Ordering,
3930 SynchronizationScope SynchScope) {
3931 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3932 Alignment = getEVTAlignment(MemVT);
3934 MachineFunction &MF = getMachineFunction();
3935 // A monotonic store does not load; a release store "loads" in the sense
3936 // that other stores cannot be sunk past it.
3937 // (An atomicrmw obviously both loads and stores.)
3938 unsigned Flags = MachineMemOperand::MOStore;
3939 if (Opcode != ISD::ATOMIC_STORE || Ordering > Monotonic)
3940 Flags |= MachineMemOperand::MOLoad;
3942 // For now, atomics are considered to be volatile always.
3943 // FIXME: Volatile isn't really correct; we should keep track of atomic
3944 // orderings in the memoperand.
3945 Flags |= MachineMemOperand::MOVolatile;
3947 MachineMemOperand *MMO =
3948 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
3949 MemVT.getStoreSize(), Alignment);
3951 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
3952 Ordering, SynchScope);
3955 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3957 SDValue Ptr, SDValue Val,
3958 MachineMemOperand *MMO,
3959 AtomicOrdering Ordering,
3960 SynchronizationScope SynchScope) {
3961 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
3962 Opcode == ISD::ATOMIC_LOAD_SUB ||
3963 Opcode == ISD::ATOMIC_LOAD_AND ||
3964 Opcode == ISD::ATOMIC_LOAD_OR ||
3965 Opcode == ISD::ATOMIC_LOAD_XOR ||
3966 Opcode == ISD::ATOMIC_LOAD_NAND ||
3967 Opcode == ISD::ATOMIC_LOAD_MIN ||
3968 Opcode == ISD::ATOMIC_LOAD_MAX ||
3969 Opcode == ISD::ATOMIC_LOAD_UMIN ||
3970 Opcode == ISD::ATOMIC_LOAD_UMAX ||
3971 Opcode == ISD::ATOMIC_SWAP ||
3972 Opcode == ISD::ATOMIC_STORE) &&
3973 "Invalid Atomic Op");
3975 EVT VT = Val.getValueType();
3977 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
3978 getVTList(VT, MVT::Other);
3979 FoldingSetNodeID ID;
3980 ID.AddInteger(MemVT.getRawBits());
3981 SDValue Ops[] = {Chain, Ptr, Val};
3982 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3984 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3985 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3986 return SDValue(E, 0);
3988 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3990 Ordering, SynchScope);
3991 CSEMap.InsertNode(N, IP);
3992 AllNodes.push_back(N);
3993 return SDValue(N, 0);
3996 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3997 EVT VT, SDValue Chain,
3999 const Value* PtrVal,
4001 AtomicOrdering Ordering,
4002 SynchronizationScope SynchScope) {
4003 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4004 Alignment = getEVTAlignment(MemVT);
4006 MachineFunction &MF = getMachineFunction();
4007 // A monotonic load does not store; an acquire load "stores" in the sense
4008 // that other loads cannot be hoisted past it.
4009 unsigned Flags = MachineMemOperand::MOLoad;
4010 if (Ordering > Monotonic)
4011 Flags |= MachineMemOperand::MOStore;
4013 // For now, atomics are considered to be volatile always.
4014 // FIXME: Volatile isn't really correct; we should keep track of atomic
4015 // orderings in the memoperand.
4016 Flags |= MachineMemOperand::MOVolatile;
4018 MachineMemOperand *MMO =
4019 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4020 MemVT.getStoreSize(), Alignment);
4022 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4023 Ordering, SynchScope);
4026 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4027 EVT VT, SDValue Chain,
4029 MachineMemOperand *MMO,
4030 AtomicOrdering Ordering,
4031 SynchronizationScope SynchScope) {
4032 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4034 SDVTList VTs = getVTList(VT, MVT::Other);
4035 FoldingSetNodeID ID;
4036 ID.AddInteger(MemVT.getRawBits());
4037 SDValue Ops[] = {Chain, Ptr};
4038 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4040 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4041 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4042 return SDValue(E, 0);
4044 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4045 Ptr, MMO, Ordering, SynchScope);
4046 CSEMap.InsertNode(N, IP);
4047 AllNodes.push_back(N);
4048 return SDValue(N, 0);
4051 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4052 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4057 SmallVector<EVT, 4> VTs;
4058 VTs.reserve(NumOps);
4059 for (unsigned i = 0; i < NumOps; ++i)
4060 VTs.push_back(Ops[i].getValueType());
4061 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4066 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4067 const EVT *VTs, unsigned NumVTs,
4068 const SDValue *Ops, unsigned NumOps,
4069 EVT MemVT, MachinePointerInfo PtrInfo,
4070 unsigned Align, bool Vol,
4071 bool ReadMem, bool WriteMem) {
4072 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4073 MemVT, PtrInfo, Align, Vol,
4078 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4079 const SDValue *Ops, unsigned NumOps,
4080 EVT MemVT, MachinePointerInfo PtrInfo,
4081 unsigned Align, bool Vol,
4082 bool ReadMem, bool WriteMem) {
4083 if (Align == 0) // Ensure that codegen never sees alignment 0
4084 Align = getEVTAlignment(MemVT);
4086 MachineFunction &MF = getMachineFunction();
4089 Flags |= MachineMemOperand::MOStore;
4091 Flags |= MachineMemOperand::MOLoad;
4093 Flags |= MachineMemOperand::MOVolatile;
4094 MachineMemOperand *MMO =
4095 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4097 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4101 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4102 const SDValue *Ops, unsigned NumOps,
4103 EVT MemVT, MachineMemOperand *MMO) {
4104 assert((Opcode == ISD::INTRINSIC_VOID ||
4105 Opcode == ISD::INTRINSIC_W_CHAIN ||
4106 Opcode == ISD::PREFETCH ||
4107 (Opcode <= INT_MAX &&
4108 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4109 "Opcode is not a memory-accessing opcode!");
4111 // Memoize the node unless it returns a flag.
4112 MemIntrinsicSDNode *N;
4113 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4114 FoldingSetNodeID ID;
4115 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4117 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4118 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4119 return SDValue(E, 0);
4122 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4124 CSEMap.InsertNode(N, IP);
4126 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4129 AllNodes.push_back(N);
4130 return SDValue(N, 0);
4133 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4134 /// MachinePointerInfo record from it. This is particularly useful because the
4135 /// code generator has many cases where it doesn't bother passing in a
4136 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4137 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4138 // If this is FI+Offset, we can model it.
4139 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4140 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4142 // If this is (FI+Offset1)+Offset2, we can model it.
4143 if (Ptr.getOpcode() != ISD::ADD ||
4144 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4145 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4146 return MachinePointerInfo();
4148 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4149 return MachinePointerInfo::getFixedStack(FI, Offset+
4150 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4153 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4154 /// MachinePointerInfo record from it. This is particularly useful because the
4155 /// code generator has many cases where it doesn't bother passing in a
4156 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4157 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4158 // If the 'Offset' value isn't a constant, we can't handle this.
4159 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4160 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4161 if (OffsetOp.getOpcode() == ISD::UNDEF)
4162 return InferPointerInfo(Ptr);
4163 return MachinePointerInfo();
4168 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4169 EVT VT, DebugLoc dl, SDValue Chain,
4170 SDValue Ptr, SDValue Offset,
4171 MachinePointerInfo PtrInfo, EVT MemVT,
4172 bool isVolatile, bool isNonTemporal, bool isInvariant,
4173 unsigned Alignment, const MDNode *TBAAInfo) {
4174 assert(Chain.getValueType() == MVT::Other &&
4175 "Invalid chain type");
4176 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4177 Alignment = getEVTAlignment(VT);
4179 unsigned Flags = MachineMemOperand::MOLoad;
4181 Flags |= MachineMemOperand::MOVolatile;
4183 Flags |= MachineMemOperand::MONonTemporal;
4185 Flags |= MachineMemOperand::MOInvariant;
4187 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4190 PtrInfo = InferPointerInfo(Ptr, Offset);
4192 MachineFunction &MF = getMachineFunction();
4193 MachineMemOperand *MMO =
4194 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4196 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4200 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4201 EVT VT, DebugLoc dl, SDValue Chain,
4202 SDValue Ptr, SDValue Offset, EVT MemVT,
4203 MachineMemOperand *MMO) {
4205 ExtType = ISD::NON_EXTLOAD;
4206 } else if (ExtType == ISD::NON_EXTLOAD) {
4207 assert(VT == MemVT && "Non-extending load from different memory type!");
4210 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4211 "Should only be an extending load, not truncating!");
4212 assert(VT.isInteger() == MemVT.isInteger() &&
4213 "Cannot convert from FP to Int or Int -> FP!");
4214 assert(VT.isVector() == MemVT.isVector() &&
4215 "Cannot use trunc store to convert to or from a vector!");
4216 assert((!VT.isVector() ||
4217 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4218 "Cannot use trunc store to change the number of vector elements!");
4221 bool Indexed = AM != ISD::UNINDEXED;
4222 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4223 "Unindexed load with an offset!");
4225 SDVTList VTs = Indexed ?
4226 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4227 SDValue Ops[] = { Chain, Ptr, Offset };
4228 FoldingSetNodeID ID;
4229 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4230 ID.AddInteger(MemVT.getRawBits());
4231 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4232 MMO->isNonTemporal(),
4233 MMO->isInvariant()));
4235 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4236 cast<LoadSDNode>(E)->refineAlignment(MMO);
4237 return SDValue(E, 0);
4239 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4241 CSEMap.InsertNode(N, IP);
4242 AllNodes.push_back(N);
4243 return SDValue(N, 0);
4246 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4247 SDValue Chain, SDValue Ptr,
4248 MachinePointerInfo PtrInfo,
4249 bool isVolatile, bool isNonTemporal,
4250 bool isInvariant, unsigned Alignment,
4251 const MDNode *TBAAInfo) {
4252 SDValue Undef = getUNDEF(Ptr.getValueType());
4253 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4254 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4258 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4259 SDValue Chain, SDValue Ptr,
4260 MachinePointerInfo PtrInfo, EVT MemVT,
4261 bool isVolatile, bool isNonTemporal,
4262 unsigned Alignment, const MDNode *TBAAInfo) {
4263 SDValue Undef = getUNDEF(Ptr.getValueType());
4264 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4265 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4271 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4272 SDValue Offset, ISD::MemIndexedMode AM) {
4273 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4274 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4275 "Load is already a indexed load!");
4276 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4277 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4278 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4279 false, LD->getAlignment());
4282 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4283 SDValue Ptr, MachinePointerInfo PtrInfo,
4284 bool isVolatile, bool isNonTemporal,
4285 unsigned Alignment, const MDNode *TBAAInfo) {
4286 assert(Chain.getValueType() == MVT::Other &&
4287 "Invalid chain type");
4288 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4289 Alignment = getEVTAlignment(Val.getValueType());
4291 unsigned Flags = MachineMemOperand::MOStore;
4293 Flags |= MachineMemOperand::MOVolatile;
4295 Flags |= MachineMemOperand::MONonTemporal;
4298 PtrInfo = InferPointerInfo(Ptr);
4300 MachineFunction &MF = getMachineFunction();
4301 MachineMemOperand *MMO =
4302 MF.getMachineMemOperand(PtrInfo, Flags,
4303 Val.getValueType().getStoreSize(), Alignment,
4306 return getStore(Chain, dl, Val, Ptr, MMO);
4309 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4310 SDValue Ptr, MachineMemOperand *MMO) {
4311 assert(Chain.getValueType() == MVT::Other &&
4312 "Invalid chain type");
4313 EVT VT = Val.getValueType();
4314 SDVTList VTs = getVTList(MVT::Other);
4315 SDValue Undef = getUNDEF(Ptr.getValueType());
4316 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4317 FoldingSetNodeID ID;
4318 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4319 ID.AddInteger(VT.getRawBits());
4320 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4321 MMO->isNonTemporal(), MMO->isInvariant()));
4323 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4324 cast<StoreSDNode>(E)->refineAlignment(MMO);
4325 return SDValue(E, 0);
4327 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4329 CSEMap.InsertNode(N, IP);
4330 AllNodes.push_back(N);
4331 return SDValue(N, 0);
4334 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4335 SDValue Ptr, MachinePointerInfo PtrInfo,
4336 EVT SVT,bool isVolatile, bool isNonTemporal,
4338 const MDNode *TBAAInfo) {
4339 assert(Chain.getValueType() == MVT::Other &&
4340 "Invalid chain type");
4341 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4342 Alignment = getEVTAlignment(SVT);
4344 unsigned Flags = MachineMemOperand::MOStore;
4346 Flags |= MachineMemOperand::MOVolatile;
4348 Flags |= MachineMemOperand::MONonTemporal;
4351 PtrInfo = InferPointerInfo(Ptr);
4353 MachineFunction &MF = getMachineFunction();
4354 MachineMemOperand *MMO =
4355 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4358 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4361 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4362 SDValue Ptr, EVT SVT,
4363 MachineMemOperand *MMO) {
4364 EVT VT = Val.getValueType();
4366 assert(Chain.getValueType() == MVT::Other &&
4367 "Invalid chain type");
4369 return getStore(Chain, dl, Val, Ptr, MMO);
4371 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4372 "Should only be a truncating store, not extending!");
4373 assert(VT.isInteger() == SVT.isInteger() &&
4374 "Can't do FP-INT conversion!");
4375 assert(VT.isVector() == SVT.isVector() &&
4376 "Cannot use trunc store to convert to or from a vector!");
4377 assert((!VT.isVector() ||
4378 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4379 "Cannot use trunc store to change the number of vector elements!");
4381 SDVTList VTs = getVTList(MVT::Other);
4382 SDValue Undef = getUNDEF(Ptr.getValueType());
4383 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4384 FoldingSetNodeID ID;
4385 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4386 ID.AddInteger(SVT.getRawBits());
4387 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4388 MMO->isNonTemporal(), MMO->isInvariant()));
4390 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4391 cast<StoreSDNode>(E)->refineAlignment(MMO);
4392 return SDValue(E, 0);
4394 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4396 CSEMap.InsertNode(N, IP);
4397 AllNodes.push_back(N);
4398 return SDValue(N, 0);
4402 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4403 SDValue Offset, ISD::MemIndexedMode AM) {
4404 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4405 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4406 "Store is already a indexed store!");
4407 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4408 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4409 FoldingSetNodeID ID;
4410 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4411 ID.AddInteger(ST->getMemoryVT().getRawBits());
4412 ID.AddInteger(ST->getRawSubclassData());
4414 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4415 return SDValue(E, 0);
4417 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4418 ST->isTruncatingStore(),
4420 ST->getMemOperand());
4421 CSEMap.InsertNode(N, IP);
4422 AllNodes.push_back(N);
4423 return SDValue(N, 0);
4426 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4427 SDValue Chain, SDValue Ptr,
4430 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4431 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4434 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4435 const SDUse *Ops, unsigned NumOps) {
4437 case 0: return getNode(Opcode, DL, VT);
4438 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4439 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4440 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4444 // Copy from an SDUse array into an SDValue array for use with
4445 // the regular getNode logic.
4446 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4447 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4450 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4451 const SDValue *Ops, unsigned NumOps) {
4453 case 0: return getNode(Opcode, DL, VT);
4454 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4455 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4456 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4462 case ISD::SELECT_CC: {
4463 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4464 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4465 "LHS and RHS of condition must have same type!");
4466 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4467 "True and False arms of SelectCC must have same type!");
4468 assert(Ops[2].getValueType() == VT &&
4469 "select_cc node must be of same type as true and false value!");
4473 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4474 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4475 "LHS/RHS of comparison should match types!");
4482 SDVTList VTs = getVTList(VT);
4484 if (VT != MVT::Glue) {
4485 FoldingSetNodeID ID;
4486 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4489 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4490 return SDValue(E, 0);
4492 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4493 CSEMap.InsertNode(N, IP);
4495 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4498 AllNodes.push_back(N);
4502 return SDValue(N, 0);
4505 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4506 const std::vector<EVT> &ResultTys,
4507 const SDValue *Ops, unsigned NumOps) {
4508 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4512 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4513 const EVT *VTs, unsigned NumVTs,
4514 const SDValue *Ops, unsigned NumOps) {
4516 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4517 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4520 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4521 const SDValue *Ops, unsigned NumOps) {
4522 if (VTList.NumVTs == 1)
4523 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4527 // FIXME: figure out how to safely handle things like
4528 // int foo(int x) { return 1 << (x & 255); }
4529 // int bar() { return foo(256); }
4530 case ISD::SRA_PARTS:
4531 case ISD::SRL_PARTS:
4532 case ISD::SHL_PARTS:
4533 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4534 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4535 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4536 else if (N3.getOpcode() == ISD::AND)
4537 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4538 // If the and is only masking out bits that cannot effect the shift,
4539 // eliminate the and.
4540 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4541 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4542 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4548 // Memoize the node unless it returns a flag.
4550 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4551 FoldingSetNodeID ID;
4552 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4554 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4555 return SDValue(E, 0);
4558 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4559 } else if (NumOps == 2) {
4560 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4561 } else if (NumOps == 3) {
4562 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4565 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4567 CSEMap.InsertNode(N, IP);
4570 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4571 } else if (NumOps == 2) {
4572 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4573 } else if (NumOps == 3) {
4574 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4577 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4580 AllNodes.push_back(N);
4584 return SDValue(N, 0);
4587 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4588 return getNode(Opcode, DL, VTList, 0, 0);
4591 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4593 SDValue Ops[] = { N1 };
4594 return getNode(Opcode, DL, VTList, Ops, 1);
4597 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4598 SDValue N1, SDValue N2) {
4599 SDValue Ops[] = { N1, N2 };
4600 return getNode(Opcode, DL, VTList, Ops, 2);
4603 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4604 SDValue N1, SDValue N2, SDValue N3) {
4605 SDValue Ops[] = { N1, N2, N3 };
4606 return getNode(Opcode, DL, VTList, Ops, 3);
4609 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4610 SDValue N1, SDValue N2, SDValue N3,
4612 SDValue Ops[] = { N1, N2, N3, N4 };
4613 return getNode(Opcode, DL, VTList, Ops, 4);
4616 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4617 SDValue N1, SDValue N2, SDValue N3,
4618 SDValue N4, SDValue N5) {
4619 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4620 return getNode(Opcode, DL, VTList, Ops, 5);
4623 SDVTList SelectionDAG::getVTList(EVT VT) {
4624 return makeVTList(SDNode::getValueTypeList(VT), 1);
4627 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4628 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4629 E = VTList.rend(); I != E; ++I)
4630 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4633 EVT *Array = Allocator.Allocate<EVT>(2);
4636 SDVTList Result = makeVTList(Array, 2);
4637 VTList.push_back(Result);
4641 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4642 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4643 E = VTList.rend(); I != E; ++I)
4644 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4648 EVT *Array = Allocator.Allocate<EVT>(3);
4652 SDVTList Result = makeVTList(Array, 3);
4653 VTList.push_back(Result);
4657 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4658 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4659 E = VTList.rend(); I != E; ++I)
4660 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4661 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4664 EVT *Array = Allocator.Allocate<EVT>(4);
4669 SDVTList Result = makeVTList(Array, 4);
4670 VTList.push_back(Result);
4674 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4676 case 0: llvm_unreachable("Cannot have nodes without results!");
4677 case 1: return getVTList(VTs[0]);
4678 case 2: return getVTList(VTs[0], VTs[1]);
4679 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4680 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4684 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4685 E = VTList.rend(); I != E; ++I) {
4686 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4689 bool NoMatch = false;
4690 for (unsigned i = 2; i != NumVTs; ++i)
4691 if (VTs[i] != I->VTs[i]) {
4699 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4700 std::copy(VTs, VTs+NumVTs, Array);
4701 SDVTList Result = makeVTList(Array, NumVTs);
4702 VTList.push_back(Result);
4707 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4708 /// specified operands. If the resultant node already exists in the DAG,
4709 /// this does not modify the specified node, instead it returns the node that
4710 /// already exists. If the resultant node does not exist in the DAG, the
4711 /// input node is returned. As a degenerate case, if you specify the same
4712 /// input operands as the node already has, the input node is returned.
4713 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4714 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4716 // Check to see if there is no change.
4717 if (Op == N->getOperand(0)) return N;
4719 // See if the modified node already exists.
4720 void *InsertPos = 0;
4721 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4724 // Nope it doesn't. Remove the node from its current place in the maps.
4726 if (!RemoveNodeFromCSEMaps(N))
4729 // Now we update the operands.
4730 N->OperandList[0].set(Op);
4732 // If this gets put into a CSE map, add it.
4733 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4737 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4738 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4740 // Check to see if there is no change.
4741 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4742 return N; // No operands changed, just return the input node.
4744 // See if the modified node already exists.
4745 void *InsertPos = 0;
4746 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4749 // Nope it doesn't. Remove the node from its current place in the maps.
4751 if (!RemoveNodeFromCSEMaps(N))
4754 // Now we update the operands.
4755 if (N->OperandList[0] != Op1)
4756 N->OperandList[0].set(Op1);
4757 if (N->OperandList[1] != Op2)
4758 N->OperandList[1].set(Op2);
4760 // If this gets put into a CSE map, add it.
4761 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4765 SDNode *SelectionDAG::
4766 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4767 SDValue Ops[] = { Op1, Op2, Op3 };
4768 return UpdateNodeOperands(N, Ops, 3);
4771 SDNode *SelectionDAG::
4772 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4773 SDValue Op3, SDValue Op4) {
4774 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4775 return UpdateNodeOperands(N, Ops, 4);
4778 SDNode *SelectionDAG::
4779 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4780 SDValue Op3, SDValue Op4, SDValue Op5) {
4781 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4782 return UpdateNodeOperands(N, Ops, 5);
4785 SDNode *SelectionDAG::
4786 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4787 assert(N->getNumOperands() == NumOps &&
4788 "Update with wrong number of operands");
4790 // Check to see if there is no change.
4791 bool AnyChange = false;
4792 for (unsigned i = 0; i != NumOps; ++i) {
4793 if (Ops[i] != N->getOperand(i)) {
4799 // No operands changed, just return the input node.
4800 if (!AnyChange) return N;
4802 // See if the modified node already exists.
4803 void *InsertPos = 0;
4804 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4807 // Nope it doesn't. Remove the node from its current place in the maps.
4809 if (!RemoveNodeFromCSEMaps(N))
4812 // Now we update the operands.
4813 for (unsigned i = 0; i != NumOps; ++i)
4814 if (N->OperandList[i] != Ops[i])
4815 N->OperandList[i].set(Ops[i]);
4817 // If this gets put into a CSE map, add it.
4818 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4822 /// DropOperands - Release the operands and set this node to have
4824 void SDNode::DropOperands() {
4825 // Unlike the code in MorphNodeTo that does this, we don't need to
4826 // watch for dead nodes here.
4827 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4833 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4836 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4838 SDVTList VTs = getVTList(VT);
4839 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4842 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4843 EVT VT, SDValue Op1) {
4844 SDVTList VTs = getVTList(VT);
4845 SDValue Ops[] = { Op1 };
4846 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4849 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4850 EVT VT, SDValue Op1,
4852 SDVTList VTs = getVTList(VT);
4853 SDValue Ops[] = { Op1, Op2 };
4854 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4857 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4858 EVT VT, SDValue Op1,
4859 SDValue Op2, SDValue Op3) {
4860 SDVTList VTs = getVTList(VT);
4861 SDValue Ops[] = { Op1, Op2, Op3 };
4862 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4865 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4866 EVT VT, const SDValue *Ops,
4868 SDVTList VTs = getVTList(VT);
4869 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4872 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4873 EVT VT1, EVT VT2, const SDValue *Ops,
4875 SDVTList VTs = getVTList(VT1, VT2);
4876 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4879 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4881 SDVTList VTs = getVTList(VT1, VT2);
4882 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4885 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4886 EVT VT1, EVT VT2, EVT VT3,
4887 const SDValue *Ops, unsigned NumOps) {
4888 SDVTList VTs = getVTList(VT1, VT2, VT3);
4889 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4892 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4893 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4894 const SDValue *Ops, unsigned NumOps) {
4895 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4896 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4899 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4902 SDVTList VTs = getVTList(VT1, VT2);
4903 SDValue Ops[] = { Op1 };
4904 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4907 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4909 SDValue Op1, SDValue Op2) {
4910 SDVTList VTs = getVTList(VT1, VT2);
4911 SDValue Ops[] = { Op1, Op2 };
4912 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4915 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4917 SDValue Op1, SDValue Op2,
4919 SDVTList VTs = getVTList(VT1, VT2);
4920 SDValue Ops[] = { Op1, Op2, Op3 };
4921 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4924 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4925 EVT VT1, EVT VT2, EVT VT3,
4926 SDValue Op1, SDValue Op2,
4928 SDVTList VTs = getVTList(VT1, VT2, VT3);
4929 SDValue Ops[] = { Op1, Op2, Op3 };
4930 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4933 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4934 SDVTList VTs, const SDValue *Ops,
4936 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
4937 // Reset the NodeID to -1.
4942 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
4943 /// the line number information on the merged node since it is not possible to
4944 /// preserve the information that operation is associated with multiple lines.
4945 /// This will make the debugger working better at -O0, were there is a higher
4946 /// probability having other instructions associated with that line.
4948 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
4949 DebugLoc NLoc = N->getDebugLoc();
4950 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
4951 N->setDebugLoc(DebugLoc());
4956 /// MorphNodeTo - This *mutates* the specified node to have the specified
4957 /// return type, opcode, and operands.
4959 /// Note that MorphNodeTo returns the resultant node. If there is already a
4960 /// node of the specified opcode and operands, it returns that node instead of
4961 /// the current one. Note that the DebugLoc need not be the same.
4963 /// Using MorphNodeTo is faster than creating a new node and swapping it in
4964 /// with ReplaceAllUsesWith both because it often avoids allocating a new
4965 /// node, and because it doesn't require CSE recalculation for any of
4966 /// the node's users.
4968 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
4969 SDVTList VTs, const SDValue *Ops,
4971 // If an identical node already exists, use it.
4973 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
4974 FoldingSetNodeID ID;
4975 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
4976 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
4977 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
4980 if (!RemoveNodeFromCSEMaps(N))
4983 // Start the morphing.
4985 N->ValueList = VTs.VTs;
4986 N->NumValues = VTs.NumVTs;
4988 // Clear the operands list, updating used nodes to remove this from their
4989 // use list. Keep track of any operands that become dead as a result.
4990 SmallPtrSet<SDNode*, 16> DeadNodeSet;
4991 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
4993 SDNode *Used = Use.getNode();
4995 if (Used->use_empty())
4996 DeadNodeSet.insert(Used);
4999 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5000 // Initialize the memory references information.
5001 MN->setMemRefs(0, 0);
5002 // If NumOps is larger than the # of operands we can have in a
5003 // MachineSDNode, reallocate the operand list.
5004 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5005 if (MN->OperandsNeedDelete)
5006 delete[] MN->OperandList;
5007 if (NumOps > array_lengthof(MN->LocalOperands))
5008 // We're creating a final node that will live unmorphed for the
5009 // remainder of the current SelectionDAG iteration, so we can allocate
5010 // the operands directly out of a pool with no recycling metadata.
5011 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5014 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5015 MN->OperandsNeedDelete = false;
5017 MN->InitOperands(MN->OperandList, Ops, NumOps);
5019 // If NumOps is larger than the # of operands we currently have, reallocate
5020 // the operand list.
5021 if (NumOps > N->NumOperands) {
5022 if (N->OperandsNeedDelete)
5023 delete[] N->OperandList;
5024 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5025 N->OperandsNeedDelete = true;
5027 N->InitOperands(N->OperandList, Ops, NumOps);
5030 // Delete any nodes that are still dead after adding the uses for the
5032 if (!DeadNodeSet.empty()) {
5033 SmallVector<SDNode *, 16> DeadNodes;
5034 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5035 E = DeadNodeSet.end(); I != E; ++I)
5036 if ((*I)->use_empty())
5037 DeadNodes.push_back(*I);
5038 RemoveDeadNodes(DeadNodes);
5042 CSEMap.InsertNode(N, IP); // Memoize the new node.
5047 /// getMachineNode - These are used for target selectors to create a new node
5048 /// with specified return type(s), MachineInstr opcode, and operands.
5050 /// Note that getMachineNode returns the resultant node. If there is already a
5051 /// node of the specified opcode and operands, it returns that node instead of
5052 /// the current one.
5054 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5055 SDVTList VTs = getVTList(VT);
5056 return getMachineNode(Opcode, dl, VTs, 0, 0);
5060 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5061 SDVTList VTs = getVTList(VT);
5062 SDValue Ops[] = { Op1 };
5063 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5067 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5068 SDValue Op1, SDValue Op2) {
5069 SDVTList VTs = getVTList(VT);
5070 SDValue Ops[] = { Op1, Op2 };
5071 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5075 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5076 SDValue Op1, SDValue Op2, SDValue Op3) {
5077 SDVTList VTs = getVTList(VT);
5078 SDValue Ops[] = { Op1, Op2, Op3 };
5079 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5083 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5084 const SDValue *Ops, unsigned NumOps) {
5085 SDVTList VTs = getVTList(VT);
5086 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5090 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5091 SDVTList VTs = getVTList(VT1, VT2);
5092 return getMachineNode(Opcode, dl, VTs, 0, 0);
5096 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5097 EVT VT1, EVT VT2, SDValue Op1) {
5098 SDVTList VTs = getVTList(VT1, VT2);
5099 SDValue Ops[] = { Op1 };
5100 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5104 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5105 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5106 SDVTList VTs = getVTList(VT1, VT2);
5107 SDValue Ops[] = { Op1, Op2 };
5108 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5112 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5113 EVT VT1, EVT VT2, SDValue Op1,
5114 SDValue Op2, SDValue Op3) {
5115 SDVTList VTs = getVTList(VT1, VT2);
5116 SDValue Ops[] = { Op1, Op2, Op3 };
5117 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5121 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5123 const SDValue *Ops, unsigned NumOps) {
5124 SDVTList VTs = getVTList(VT1, VT2);
5125 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5129 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5130 EVT VT1, EVT VT2, EVT VT3,
5131 SDValue Op1, SDValue Op2) {
5132 SDVTList VTs = getVTList(VT1, VT2, VT3);
5133 SDValue Ops[] = { Op1, Op2 };
5134 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5138 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5139 EVT VT1, EVT VT2, EVT VT3,
5140 SDValue Op1, SDValue Op2, SDValue Op3) {
5141 SDVTList VTs = getVTList(VT1, VT2, VT3);
5142 SDValue Ops[] = { Op1, Op2, Op3 };
5143 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5147 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5148 EVT VT1, EVT VT2, EVT VT3,
5149 const SDValue *Ops, unsigned NumOps) {
5150 SDVTList VTs = getVTList(VT1, VT2, VT3);
5151 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5155 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5156 EVT VT2, EVT VT3, EVT VT4,
5157 const SDValue *Ops, unsigned NumOps) {
5158 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5159 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5163 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5164 const std::vector<EVT> &ResultTys,
5165 const SDValue *Ops, unsigned NumOps) {
5166 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5167 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5171 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5172 const SDValue *Ops, unsigned NumOps) {
5173 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5178 FoldingSetNodeID ID;
5179 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5181 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5182 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5186 // Allocate a new MachineSDNode.
5187 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5189 // Initialize the operands list.
5190 if (NumOps > array_lengthof(N->LocalOperands))
5191 // We're creating a final node that will live unmorphed for the
5192 // remainder of the current SelectionDAG iteration, so we can allocate
5193 // the operands directly out of a pool with no recycling metadata.
5194 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5197 N->InitOperands(N->LocalOperands, Ops, NumOps);
5198 N->OperandsNeedDelete = false;
5201 CSEMap.InsertNode(N, IP);
5203 AllNodes.push_back(N);
5205 VerifyMachineNode(N);
5210 /// getTargetExtractSubreg - A convenience function for creating
5211 /// TargetOpcode::EXTRACT_SUBREG nodes.
5213 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5215 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5216 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5217 VT, Operand, SRIdxVal);
5218 return SDValue(Subreg, 0);
5221 /// getTargetInsertSubreg - A convenience function for creating
5222 /// TargetOpcode::INSERT_SUBREG nodes.
5224 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5225 SDValue Operand, SDValue Subreg) {
5226 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5227 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5228 VT, Operand, Subreg, SRIdxVal);
5229 return SDValue(Result, 0);
5232 /// getNodeIfExists - Get the specified node if it's already available, or
5233 /// else return NULL.
5234 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5235 const SDValue *Ops, unsigned NumOps) {
5236 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5237 FoldingSetNodeID ID;
5238 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5240 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5246 /// getDbgValue - Creates a SDDbgValue node.
5249 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5250 DebugLoc DL, unsigned O) {
5251 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5255 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5256 DebugLoc DL, unsigned O) {
5257 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5261 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5262 DebugLoc DL, unsigned O) {
5263 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5268 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5269 /// pointed to by a use iterator is deleted, increment the use iterator
5270 /// so that it doesn't dangle.
5272 /// This class also manages a "downlink" DAGUpdateListener, to forward
5273 /// messages to ReplaceAllUsesWith's callers.
5275 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5276 SelectionDAG::DAGUpdateListener *DownLink;
5277 SDNode::use_iterator &UI;
5278 SDNode::use_iterator &UE;
5280 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5281 // Increment the iterator as needed.
5282 while (UI != UE && N == *UI)
5285 // Then forward the message.
5286 if (DownLink) DownLink->NodeDeleted(N, E);
5289 virtual void NodeUpdated(SDNode *N) {
5290 // Just forward the message.
5291 if (DownLink) DownLink->NodeUpdated(N);
5295 RAUWUpdateListener(SelectionDAG::DAGUpdateListener *dl,
5296 SDNode::use_iterator &ui,
5297 SDNode::use_iterator &ue)
5298 : DownLink(dl), UI(ui), UE(ue) {}
5303 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5304 /// This can cause recursive merging of nodes in the DAG.
5306 /// This version assumes From has a single result value.
5308 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To,
5309 DAGUpdateListener *UpdateListener) {
5310 SDNode *From = FromN.getNode();
5311 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5312 "Cannot replace with this method!");
5313 assert(From != To.getNode() && "Cannot replace uses of with self");
5315 // Iterate over all the existing uses of From. New uses will be added
5316 // to the beginning of the use list, which we avoid visiting.
5317 // This specifically avoids visiting uses of From that arise while the
5318 // replacement is happening, because any such uses would be the result
5319 // of CSE: If an existing node looks like From after one of its operands
5320 // is replaced by To, we don't want to replace of all its users with To
5321 // too. See PR3018 for more info.
5322 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5323 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5327 // This node is about to morph, remove its old self from the CSE maps.
5328 RemoveNodeFromCSEMaps(User);
5330 // A user can appear in a use list multiple times, and when this
5331 // happens the uses are usually next to each other in the list.
5332 // To help reduce the number of CSE recomputations, process all
5333 // the uses of this user that we can find this way.
5335 SDUse &Use = UI.getUse();
5338 } while (UI != UE && *UI == User);
5340 // Now that we have modified User, add it back to the CSE maps. If it
5341 // already exists there, recursively merge the results together.
5342 AddModifiedNodeToCSEMaps(User, &Listener);
5345 // If we just RAUW'd the root, take note.
5346 if (FromN == getRoot())
5350 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5351 /// This can cause recursive merging of nodes in the DAG.
5353 /// This version assumes that for each value of From, there is a
5354 /// corresponding value in To in the same position with the same type.
5356 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
5357 DAGUpdateListener *UpdateListener) {
5359 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5360 assert((!From->hasAnyUseOfValue(i) ||
5361 From->getValueType(i) == To->getValueType(i)) &&
5362 "Cannot use this version of ReplaceAllUsesWith!");
5365 // Handle the trivial case.
5369 // Iterate over just the existing users of From. See the comments in
5370 // the ReplaceAllUsesWith above.
5371 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5372 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5376 // This node is about to morph, remove its old self from the CSE maps.
5377 RemoveNodeFromCSEMaps(User);
5379 // A user can appear in a use list multiple times, and when this
5380 // happens the uses are usually next to each other in the list.
5381 // To help reduce the number of CSE recomputations, process all
5382 // the uses of this user that we can find this way.
5384 SDUse &Use = UI.getUse();
5387 } while (UI != UE && *UI == User);
5389 // Now that we have modified User, add it back to the CSE maps. If it
5390 // already exists there, recursively merge the results together.
5391 AddModifiedNodeToCSEMaps(User, &Listener);
5394 // If we just RAUW'd the root, take note.
5395 if (From == getRoot().getNode())
5396 setRoot(SDValue(To, getRoot().getResNo()));
5399 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5400 /// This can cause recursive merging of nodes in the DAG.
5402 /// This version can replace From with any result values. To must match the
5403 /// number and types of values returned by From.
5404 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
5406 DAGUpdateListener *UpdateListener) {
5407 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5408 return ReplaceAllUsesWith(SDValue(From, 0), To[0], UpdateListener);
5410 // Iterate over just the existing users of From. See the comments in
5411 // the ReplaceAllUsesWith above.
5412 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5413 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5417 // This node is about to morph, remove its old self from the CSE maps.
5418 RemoveNodeFromCSEMaps(User);
5420 // A user can appear in a use list multiple times, and when this
5421 // happens the uses are usually next to each other in the list.
5422 // To help reduce the number of CSE recomputations, process all
5423 // the uses of this user that we can find this way.
5425 SDUse &Use = UI.getUse();
5426 const SDValue &ToOp = To[Use.getResNo()];
5429 } while (UI != UE && *UI == User);
5431 // Now that we have modified User, add it back to the CSE maps. If it
5432 // already exists there, recursively merge the results together.
5433 AddModifiedNodeToCSEMaps(User, &Listener);
5436 // If we just RAUW'd the root, take note.
5437 if (From == getRoot().getNode())
5438 setRoot(SDValue(To[getRoot().getResNo()]));
5441 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5442 /// uses of other values produced by From.getNode() alone. The Deleted
5443 /// vector is handled the same way as for ReplaceAllUsesWith.
5444 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
5445 DAGUpdateListener *UpdateListener){
5446 // Handle the really simple, really trivial case efficiently.
5447 if (From == To) return;
5449 // Handle the simple, trivial, case efficiently.
5450 if (From.getNode()->getNumValues() == 1) {
5451 ReplaceAllUsesWith(From, To, UpdateListener);
5455 // Iterate over just the existing users of From. See the comments in
5456 // the ReplaceAllUsesWith above.
5457 SDNode::use_iterator UI = From.getNode()->use_begin(),
5458 UE = From.getNode()->use_end();
5459 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5462 bool UserRemovedFromCSEMaps = false;
5464 // A user can appear in a use list multiple times, and when this
5465 // happens the uses are usually next to each other in the list.
5466 // To help reduce the number of CSE recomputations, process all
5467 // the uses of this user that we can find this way.
5469 SDUse &Use = UI.getUse();
5471 // Skip uses of different values from the same node.
5472 if (Use.getResNo() != From.getResNo()) {
5477 // If this node hasn't been modified yet, it's still in the CSE maps,
5478 // so remove its old self from the CSE maps.
5479 if (!UserRemovedFromCSEMaps) {
5480 RemoveNodeFromCSEMaps(User);
5481 UserRemovedFromCSEMaps = true;
5486 } while (UI != UE && *UI == User);
5488 // We are iterating over all uses of the From node, so if a use
5489 // doesn't use the specific value, no changes are made.
5490 if (!UserRemovedFromCSEMaps)
5493 // Now that we have modified User, add it back to the CSE maps. If it
5494 // already exists there, recursively merge the results together.
5495 AddModifiedNodeToCSEMaps(User, &Listener);
5498 // If we just RAUW'd the root, take note.
5499 if (From == getRoot())
5504 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5505 /// to record information about a use.
5512 /// operator< - Sort Memos by User.
5513 bool operator<(const UseMemo &L, const UseMemo &R) {
5514 return (intptr_t)L.User < (intptr_t)R.User;
5518 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5519 /// uses of other values produced by From.getNode() alone. The same value
5520 /// may appear in both the From and To list. The Deleted vector is
5521 /// handled the same way as for ReplaceAllUsesWith.
5522 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5525 DAGUpdateListener *UpdateListener){
5526 // Handle the simple, trivial case efficiently.
5528 return ReplaceAllUsesOfValueWith(*From, *To, UpdateListener);
5530 // Read up all the uses and make records of them. This helps
5531 // processing new uses that are introduced during the
5532 // replacement process.
5533 SmallVector<UseMemo, 4> Uses;
5534 for (unsigned i = 0; i != Num; ++i) {
5535 unsigned FromResNo = From[i].getResNo();
5536 SDNode *FromNode = From[i].getNode();
5537 for (SDNode::use_iterator UI = FromNode->use_begin(),
5538 E = FromNode->use_end(); UI != E; ++UI) {
5539 SDUse &Use = UI.getUse();
5540 if (Use.getResNo() == FromResNo) {
5541 UseMemo Memo = { *UI, i, &Use };
5542 Uses.push_back(Memo);
5547 // Sort the uses, so that all the uses from a given User are together.
5548 std::sort(Uses.begin(), Uses.end());
5550 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5551 UseIndex != UseIndexEnd; ) {
5552 // We know that this user uses some value of From. If it is the right
5553 // value, update it.
5554 SDNode *User = Uses[UseIndex].User;
5556 // This node is about to morph, remove its old self from the CSE maps.
5557 RemoveNodeFromCSEMaps(User);
5559 // The Uses array is sorted, so all the uses for a given User
5560 // are next to each other in the list.
5561 // To help reduce the number of CSE recomputations, process all
5562 // the uses of this user that we can find this way.
5564 unsigned i = Uses[UseIndex].Index;
5565 SDUse &Use = *Uses[UseIndex].Use;
5569 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5571 // Now that we have modified User, add it back to the CSE maps. If it
5572 // already exists there, recursively merge the results together.
5573 AddModifiedNodeToCSEMaps(User, UpdateListener);
5577 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5578 /// based on their topological order. It returns the maximum id and a vector
5579 /// of the SDNodes* in assigned order by reference.
5580 unsigned SelectionDAG::AssignTopologicalOrder() {
5582 unsigned DAGSize = 0;
5584 // SortedPos tracks the progress of the algorithm. Nodes before it are
5585 // sorted, nodes after it are unsorted. When the algorithm completes
5586 // it is at the end of the list.
5587 allnodes_iterator SortedPos = allnodes_begin();
5589 // Visit all the nodes. Move nodes with no operands to the front of
5590 // the list immediately. Annotate nodes that do have operands with their
5591 // operand count. Before we do this, the Node Id fields of the nodes
5592 // may contain arbitrary values. After, the Node Id fields for nodes
5593 // before SortedPos will contain the topological sort index, and the
5594 // Node Id fields for nodes At SortedPos and after will contain the
5595 // count of outstanding operands.
5596 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5599 unsigned Degree = N->getNumOperands();
5601 // A node with no uses, add it to the result array immediately.
5602 N->setNodeId(DAGSize++);
5603 allnodes_iterator Q = N;
5605 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5606 assert(SortedPos != AllNodes.end() && "Overran node list");
5609 // Temporarily use the Node Id as scratch space for the degree count.
5610 N->setNodeId(Degree);
5614 // Visit all the nodes. As we iterate, moves nodes into sorted order,
5615 // such that by the time the end is reached all nodes will be sorted.
5616 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5619 // N is in sorted position, so all its uses have one less operand
5620 // that needs to be sorted.
5621 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5624 unsigned Degree = P->getNodeId();
5625 assert(Degree != 0 && "Invalid node degree");
5628 // All of P's operands are sorted, so P may sorted now.
5629 P->setNodeId(DAGSize++);
5631 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5632 assert(SortedPos != AllNodes.end() && "Overran node list");
5635 // Update P's outstanding operand count.
5636 P->setNodeId(Degree);
5639 if (I == SortedPos) {
5642 dbgs() << "Overran sorted position:\n";
5645 llvm_unreachable(0);
5649 assert(SortedPos == AllNodes.end() &&
5650 "Topological sort incomplete!");
5651 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5652 "First node in topological sort is not the entry token!");
5653 assert(AllNodes.front().getNodeId() == 0 &&
5654 "First node in topological sort has non-zero id!");
5655 assert(AllNodes.front().getNumOperands() == 0 &&
5656 "First node in topological sort has operands!");
5657 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5658 "Last node in topologic sort has unexpected id!");
5659 assert(AllNodes.back().use_empty() &&
5660 "Last node in topologic sort has users!");
5661 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5665 /// AssignOrdering - Assign an order to the SDNode.
5666 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5667 assert(SD && "Trying to assign an order to a null node!");
5668 Ordering->add(SD, Order);
5671 /// GetOrdering - Get the order for the SDNode.
5672 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5673 assert(SD && "Trying to get the order of a null node!");
5674 return Ordering->getOrder(SD);
5677 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5678 /// value is produced by SD.
5679 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5680 DbgInfo->add(DB, SD, isParameter);
5682 SD->setHasDebugValue(true);
5685 /// TransferDbgValues - Transfer SDDbgValues.
5686 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5687 if (From == To || !From.getNode()->getHasDebugValue())
5689 SDNode *FromNode = From.getNode();
5690 SDNode *ToNode = To.getNode();
5691 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5692 SmallVector<SDDbgValue *, 2> ClonedDVs;
5693 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5695 SDDbgValue *Dbg = *I;
5696 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5697 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5698 Dbg->getOffset(), Dbg->getDebugLoc(),
5700 ClonedDVs.push_back(Clone);
5703 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5704 E = ClonedDVs.end(); I != E; ++I)
5705 AddDbgValue(*I, ToNode, false);
5708 //===----------------------------------------------------------------------===//
5710 //===----------------------------------------------------------------------===//
5712 HandleSDNode::~HandleSDNode() {
5716 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5717 const GlobalValue *GA,
5718 EVT VT, int64_t o, unsigned char TF)
5719 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5723 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5724 MachineMemOperand *mmo)
5725 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5726 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5727 MMO->isNonTemporal(), MMO->isInvariant());
5728 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5729 assert(isNonTemporal() == MMO->isNonTemporal() &&
5730 "Non-temporal encoding error!");
5731 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5734 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5735 const SDValue *Ops, unsigned NumOps, EVT memvt,
5736 MachineMemOperand *mmo)
5737 : SDNode(Opc, dl, VTs, Ops, NumOps),
5738 MemoryVT(memvt), MMO(mmo) {
5739 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5740 MMO->isNonTemporal(), MMO->isInvariant());
5741 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5742 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5745 /// Profile - Gather unique data for the node.
5747 void SDNode::Profile(FoldingSetNodeID &ID) const {
5748 AddNodeIDNode(ID, this);
5753 std::vector<EVT> VTs;
5756 VTs.reserve(MVT::LAST_VALUETYPE);
5757 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5758 VTs.push_back(MVT((MVT::SimpleValueType)i));
5763 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5764 static ManagedStatic<EVTArray> SimpleVTArray;
5765 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5767 /// getValueTypeList - Return a pointer to the specified value type.
5769 const EVT *SDNode::getValueTypeList(EVT VT) {
5770 if (VT.isExtended()) {
5771 sys::SmartScopedLock<true> Lock(*VTMutex);
5772 return &(*EVTs->insert(VT).first);
5774 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5775 "Value type out of range!");
5776 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5780 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5781 /// indicated value. This method ignores uses of other values defined by this
5783 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5784 assert(Value < getNumValues() && "Bad value!");
5786 // TODO: Only iterate over uses of a given value of the node
5787 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5788 if (UI.getUse().getResNo() == Value) {
5795 // Found exactly the right number of uses?
5800 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5801 /// value. This method ignores uses of other values defined by this operation.
5802 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5803 assert(Value < getNumValues() && "Bad value!");
5805 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5806 if (UI.getUse().getResNo() == Value)
5813 /// isOnlyUserOf - Return true if this node is the only use of N.
5815 bool SDNode::isOnlyUserOf(SDNode *N) const {
5817 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5828 /// isOperand - Return true if this node is an operand of N.
5830 bool SDValue::isOperandOf(SDNode *N) const {
5831 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5832 if (*this == N->getOperand(i))
5837 bool SDNode::isOperandOf(SDNode *N) const {
5838 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5839 if (this == N->OperandList[i].getNode())
5844 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5845 /// be a chain) reaches the specified operand without crossing any
5846 /// side-effecting instructions on any chain path. In practice, this looks
5847 /// through token factors and non-volatile loads. In order to remain efficient,
5848 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5849 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5850 unsigned Depth) const {
5851 if (*this == Dest) return true;
5853 // Don't search too deeply, we just want to be able to see through
5854 // TokenFactor's etc.
5855 if (Depth == 0) return false;
5857 // If this is a token factor, all inputs to the TF happen in parallel. If any
5858 // of the operands of the TF does not reach dest, then we cannot do the xform.
5859 if (getOpcode() == ISD::TokenFactor) {
5860 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5861 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5866 // Loads don't have side effects, look through them.
5867 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5868 if (!Ld->isVolatile())
5869 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5874 /// hasPredecessor - Return true if N is a predecessor of this node.
5875 /// N is either an operand of this node, or can be reached by recursively
5876 /// traversing up the operands.
5877 /// NOTE: This is an expensive method. Use it carefully.
5878 bool SDNode::hasPredecessor(const SDNode *N) const {
5879 SmallPtrSet<const SDNode *, 32> Visited;
5880 SmallVector<const SDNode *, 16> Worklist;
5881 return hasPredecessorHelper(N, Visited, Worklist);
5884 bool SDNode::hasPredecessorHelper(const SDNode *N,
5885 SmallPtrSet<const SDNode *, 32> &Visited,
5886 SmallVector<const SDNode *, 16> &Worklist) const {
5887 if (Visited.empty()) {
5888 Worklist.push_back(this);
5890 // Take a look in the visited set. If we've already encountered this node
5891 // we needn't search further.
5892 if (Visited.count(N))
5896 // Haven't visited N yet. Continue the search.
5897 while (!Worklist.empty()) {
5898 const SDNode *M = Worklist.pop_back_val();
5899 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5900 SDNode *Op = M->getOperand(i).getNode();
5901 if (Visited.insert(Op))
5902 Worklist.push_back(Op);
5911 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5912 assert(Num < NumOperands && "Invalid child # of SDNode!");
5913 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5916 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
5917 assert(N->getNumValues() == 1 &&
5918 "Can't unroll a vector with multiple results!");
5920 EVT VT = N->getValueType(0);
5921 unsigned NE = VT.getVectorNumElements();
5922 EVT EltVT = VT.getVectorElementType();
5923 DebugLoc dl = N->getDebugLoc();
5925 SmallVector<SDValue, 8> Scalars;
5926 SmallVector<SDValue, 4> Operands(N->getNumOperands());
5928 // If ResNE is 0, fully unroll the vector op.
5931 else if (NE > ResNE)
5935 for (i= 0; i != NE; ++i) {
5936 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
5937 SDValue Operand = N->getOperand(j);
5938 EVT OperandVT = Operand.getValueType();
5939 if (OperandVT.isVector()) {
5940 // A vector operand; extract a single element.
5941 EVT OperandEltVT = OperandVT.getVectorElementType();
5942 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
5945 getConstant(i, TLI.getPointerTy()));
5947 // A scalar operand; just use it as is.
5948 Operands[j] = Operand;
5952 switch (N->getOpcode()) {
5954 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5955 &Operands[0], Operands.size()));
5958 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
5959 &Operands[0], Operands.size()));
5966 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
5967 getShiftAmountOperand(Operands[0].getValueType(),
5970 case ISD::SIGN_EXTEND_INREG:
5971 case ISD::FP_ROUND_INREG: {
5972 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
5973 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5975 getValueType(ExtVT)));
5980 for (; i < ResNE; ++i)
5981 Scalars.push_back(getUNDEF(EltVT));
5983 return getNode(ISD::BUILD_VECTOR, dl,
5984 EVT::getVectorVT(*getContext(), EltVT, ResNE),
5985 &Scalars[0], Scalars.size());
5989 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
5990 /// location that is 'Dist' units away from the location that the 'Base' load
5991 /// is loading from.
5992 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
5993 unsigned Bytes, int Dist) const {
5994 if (LD->getChain() != Base->getChain())
5996 EVT VT = LD->getValueType(0);
5997 if (VT.getSizeInBits() / 8 != Bytes)
6000 SDValue Loc = LD->getOperand(1);
6001 SDValue BaseLoc = Base->getOperand(1);
6002 if (Loc.getOpcode() == ISD::FrameIndex) {
6003 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6005 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6006 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6007 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6008 int FS = MFI->getObjectSize(FI);
6009 int BFS = MFI->getObjectSize(BFI);
6010 if (FS != BFS || FS != (int)Bytes) return false;
6011 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6015 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6016 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6019 const GlobalValue *GV1 = NULL;
6020 const GlobalValue *GV2 = NULL;
6021 int64_t Offset1 = 0;
6022 int64_t Offset2 = 0;
6023 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6024 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6025 if (isGA1 && isGA2 && GV1 == GV2)
6026 return Offset1 == (Offset2 + Dist*Bytes);
6031 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6032 /// it cannot be inferred.
6033 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6034 // If this is a GlobalAddress + cst, return the alignment.
6035 const GlobalValue *GV;
6036 int64_t GVOffset = 0;
6037 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6038 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6039 APInt AllOnes = APInt::getAllOnesValue(PtrWidth);
6040 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6041 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), AllOnes,
6042 KnownZero, KnownOne, TLI.getTargetData());
6043 unsigned AlignBits = KnownZero.countTrailingOnes();
6044 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6046 return MinAlign(Align, GVOffset);
6049 // If this is a direct reference to a stack slot, use information about the
6050 // stack slot's alignment.
6051 int FrameIdx = 1 << 31;
6052 int64_t FrameOffset = 0;
6053 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6054 FrameIdx = FI->getIndex();
6055 } else if (isBaseWithConstantOffset(Ptr) &&
6056 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6058 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6059 FrameOffset = Ptr.getConstantOperandVal(1);
6062 if (FrameIdx != (1 << 31)) {
6063 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6064 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6072 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6073 unsigned GlobalAddressSDNode::getAddressSpace() const {
6074 return getGlobal()->getType()->getAddressSpace();
6078 Type *ConstantPoolSDNode::getType() const {
6079 if (isMachineConstantPoolEntry())
6080 return Val.MachineCPVal->getType();
6081 return Val.ConstVal->getType();
6084 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6086 unsigned &SplatBitSize,
6088 unsigned MinSplatBits,
6090 EVT VT = getValueType(0);
6091 assert(VT.isVector() && "Expected a vector type");
6092 unsigned sz = VT.getSizeInBits();
6093 if (MinSplatBits > sz)
6096 SplatValue = APInt(sz, 0);
6097 SplatUndef = APInt(sz, 0);
6099 // Get the bits. Bits with undefined values (when the corresponding element
6100 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6101 // in SplatValue. If any of the values are not constant, give up and return
6103 unsigned int nOps = getNumOperands();
6104 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6105 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6107 for (unsigned j = 0; j < nOps; ++j) {
6108 unsigned i = isBigEndian ? nOps-1-j : j;
6109 SDValue OpVal = getOperand(i);
6110 unsigned BitPos = j * EltBitSize;
6112 if (OpVal.getOpcode() == ISD::UNDEF)
6113 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6114 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6115 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6116 zextOrTrunc(sz) << BitPos;
6117 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6118 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6123 // The build_vector is all constants or undefs. Find the smallest element
6124 // size that splats the vector.
6126 HasAnyUndefs = (SplatUndef != 0);
6129 unsigned HalfSize = sz / 2;
6130 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6131 APInt LowValue = SplatValue.trunc(HalfSize);
6132 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6133 APInt LowUndef = SplatUndef.trunc(HalfSize);
6135 // If the two halves do not match (ignoring undef bits), stop here.
6136 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6137 MinSplatBits > HalfSize)
6140 SplatValue = HighValue | LowValue;
6141 SplatUndef = HighUndef & LowUndef;
6150 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6151 // Find the first non-undef value in the shuffle mask.
6153 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6156 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6158 // Make sure all remaining elements are either undef or the same as the first
6160 for (int Idx = Mask[i]; i != e; ++i)
6161 if (Mask[i] >= 0 && Mask[i] != Idx)
6167 static void checkForCyclesHelper(const SDNode *N,
6168 SmallPtrSet<const SDNode*, 32> &Visited,
6169 SmallPtrSet<const SDNode*, 32> &Checked) {
6170 // If this node has already been checked, don't check it again.
6171 if (Checked.count(N))
6174 // If a node has already been visited on this depth-first walk, reject it as
6176 if (!Visited.insert(N)) {
6177 dbgs() << "Offending node:\n";
6179 errs() << "Detected cycle in SelectionDAG\n";
6183 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6184 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6191 void llvm::checkForCycles(const llvm::SDNode *N) {
6193 assert(N && "Checking nonexistant SDNode");
6194 SmallPtrSet<const SDNode*, 32> visited;
6195 SmallPtrSet<const SDNode*, 32> checked;
6196 checkForCyclesHelper(N, visited, checked);
6200 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6201 checkForCycles(DAG->getRoot().getNode());