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 "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/TargetTransformInfo.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/Assembly/Writer.h"
24 #include "llvm/CodeGen/MachineBasicBlock.h"
25 #include "llvm/CodeGen/MachineConstantPool.h"
26 #include "llvm/CodeGen/MachineFrameInfo.h"
27 #include "llvm/CodeGen/MachineModuleInfo.h"
28 #include "llvm/DebugInfo.h"
29 #include "llvm/IR/CallingConv.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/DataLayout.h"
32 #include "llvm/IR/DerivedTypes.h"
33 #include "llvm/IR/Function.h"
34 #include "llvm/IR/GlobalAlias.h"
35 #include "llvm/IR/GlobalVariable.h"
36 #include "llvm/IR/Intrinsics.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/ErrorHandling.h"
40 #include "llvm/Support/ManagedStatic.h"
41 #include "llvm/Support/MathExtras.h"
42 #include "llvm/Support/Mutex.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include "llvm/Target/TargetInstrInfo.h"
45 #include "llvm/Target/TargetIntrinsicInfo.h"
46 #include "llvm/Target/TargetLowering.h"
47 #include "llvm/Target/TargetMachine.h"
48 #include "llvm/Target/TargetOptions.h"
49 #include "llvm/Target/TargetRegisterInfo.h"
50 #include "llvm/Target/TargetSelectionDAGInfo.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 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 if (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 if (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 unsigned i = 0, e = N->getNumOperands();
154 // Skip over all of the undef values.
155 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept an all-undef vector.
159 if (i == e) return false;
161 // Do not accept build_vectors that aren't all constants or which have non-0
163 SDValue Zero = N->getOperand(i);
164 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
165 if (!CN->isNullValue())
167 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
168 if (!CFPN->getValueAPF().isPosZero())
173 // Okay, we have at least one 0 value, check to see if the rest match or are
175 for (++i; i != e; ++i)
176 if (N->getOperand(i) != Zero &&
177 N->getOperand(i).getOpcode() != ISD::UNDEF)
182 /// isScalarToVector - Return true if the specified node is a
183 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
184 /// element is not an undef.
185 bool ISD::isScalarToVector(const SDNode *N) {
186 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
189 if (N->getOpcode() != ISD::BUILD_VECTOR)
191 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
193 unsigned NumElems = N->getNumOperands();
196 for (unsigned i = 1; i < NumElems; ++i) {
197 SDValue V = N->getOperand(i);
198 if (V.getOpcode() != ISD::UNDEF)
204 /// allOperandsUndef - Return true if the node has at least one operand
205 /// and all operands of the specified node are ISD::UNDEF.
206 bool ISD::allOperandsUndef(const SDNode *N) {
207 // Return false if the node has no operands.
208 // This is "logically inconsistent" with the definition of "all" but
209 // is probably the desired behavior.
210 if (N->getNumOperands() == 0)
213 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
214 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
220 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
221 /// when given the operation for (X op Y).
222 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
223 // To perform this operation, we just need to swap the L and G bits of the
225 unsigned OldL = (Operation >> 2) & 1;
226 unsigned OldG = (Operation >> 1) & 1;
227 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
228 (OldL << 1) | // New G bit
229 (OldG << 2)); // New L bit.
232 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
233 /// 'op' is a valid SetCC operation.
234 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
235 unsigned Operation = Op;
237 Operation ^= 7; // Flip L, G, E bits, but not U.
239 Operation ^= 15; // Flip all of the condition bits.
241 if (Operation > ISD::SETTRUE2)
242 Operation &= ~8; // Don't let N and U bits get set.
244 return ISD::CondCode(Operation);
248 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
249 /// signed operation and 2 if the result is an unsigned comparison. Return zero
250 /// if the operation does not depend on the sign of the input (setne and seteq).
251 static int isSignedOp(ISD::CondCode Opcode) {
253 default: llvm_unreachable("Illegal integer setcc operation!");
255 case ISD::SETNE: return 0;
259 case ISD::SETGE: return 1;
263 case ISD::SETUGE: return 2;
267 /// getSetCCOrOperation - Return the result of a logical OR between different
268 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
269 /// returns SETCC_INVALID if it is not possible to represent the resultant
271 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
273 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
274 // Cannot fold a signed integer setcc with an unsigned integer setcc.
275 return ISD::SETCC_INVALID;
277 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
279 // If the N and U bits get set then the resultant comparison DOES suddenly
280 // care about orderedness, and is true when ordered.
281 if (Op > ISD::SETTRUE2)
282 Op &= ~16; // Clear the U bit if the N bit is set.
284 // Canonicalize illegal integer setcc's.
285 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
288 return ISD::CondCode(Op);
291 /// getSetCCAndOperation - Return the result of a logical AND between different
292 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
293 /// function returns zero if it is not possible to represent the resultant
295 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
297 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
298 // Cannot fold a signed setcc with an unsigned setcc.
299 return ISD::SETCC_INVALID;
301 // Combine all of the condition bits.
302 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
304 // Canonicalize illegal integer setcc's.
308 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
309 case ISD::SETOEQ: // SETEQ & SETU[LG]E
310 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
311 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
312 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
319 //===----------------------------------------------------------------------===//
320 // SDNode Profile Support
321 //===----------------------------------------------------------------------===//
323 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
325 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
329 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
330 /// solely with their pointer.
331 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
332 ID.AddPointer(VTList.VTs);
335 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
337 static void AddNodeIDOperands(FoldingSetNodeID &ID,
338 const SDValue *Ops, unsigned NumOps) {
339 for (; NumOps; --NumOps, ++Ops) {
340 ID.AddPointer(Ops->getNode());
341 ID.AddInteger(Ops->getResNo());
345 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
347 static void AddNodeIDOperands(FoldingSetNodeID &ID,
348 const SDUse *Ops, unsigned NumOps) {
349 for (; NumOps; --NumOps, ++Ops) {
350 ID.AddPointer(Ops->getNode());
351 ID.AddInteger(Ops->getResNo());
355 static void AddNodeIDNode(FoldingSetNodeID &ID,
356 unsigned short OpC, SDVTList VTList,
357 const SDValue *OpList, unsigned N) {
358 AddNodeIDOpcode(ID, OpC);
359 AddNodeIDValueTypes(ID, VTList);
360 AddNodeIDOperands(ID, OpList, N);
363 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
365 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
366 switch (N->getOpcode()) {
367 case ISD::TargetExternalSymbol:
368 case ISD::ExternalSymbol:
369 llvm_unreachable("Should only be used on nodes with operands");
370 default: break; // Normal nodes don't need extra info.
371 case ISD::TargetConstant:
373 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
375 case ISD::TargetConstantFP:
376 case ISD::ConstantFP: {
377 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
380 case ISD::TargetGlobalAddress:
381 case ISD::GlobalAddress:
382 case ISD::TargetGlobalTLSAddress:
383 case ISD::GlobalTLSAddress: {
384 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
385 ID.AddPointer(GA->getGlobal());
386 ID.AddInteger(GA->getOffset());
387 ID.AddInteger(GA->getTargetFlags());
388 ID.AddInteger(GA->getAddressSpace());
391 case ISD::BasicBlock:
392 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
395 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
397 case ISD::RegisterMask:
398 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
401 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
403 case ISD::FrameIndex:
404 case ISD::TargetFrameIndex:
405 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
408 case ISD::TargetJumpTable:
409 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
410 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
412 case ISD::ConstantPool:
413 case ISD::TargetConstantPool: {
414 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
415 ID.AddInteger(CP->getAlignment());
416 ID.AddInteger(CP->getOffset());
417 if (CP->isMachineConstantPoolEntry())
418 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
420 ID.AddPointer(CP->getConstVal());
421 ID.AddInteger(CP->getTargetFlags());
424 case ISD::TargetIndex: {
425 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
426 ID.AddInteger(TI->getIndex());
427 ID.AddInteger(TI->getOffset());
428 ID.AddInteger(TI->getTargetFlags());
432 const LoadSDNode *LD = cast<LoadSDNode>(N);
433 ID.AddInteger(LD->getMemoryVT().getRawBits());
434 ID.AddInteger(LD->getRawSubclassData());
435 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
439 const StoreSDNode *ST = cast<StoreSDNode>(N);
440 ID.AddInteger(ST->getMemoryVT().getRawBits());
441 ID.AddInteger(ST->getRawSubclassData());
442 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
445 case ISD::ATOMIC_CMP_SWAP:
446 case ISD::ATOMIC_SWAP:
447 case ISD::ATOMIC_LOAD_ADD:
448 case ISD::ATOMIC_LOAD_SUB:
449 case ISD::ATOMIC_LOAD_AND:
450 case ISD::ATOMIC_LOAD_OR:
451 case ISD::ATOMIC_LOAD_XOR:
452 case ISD::ATOMIC_LOAD_NAND:
453 case ISD::ATOMIC_LOAD_MIN:
454 case ISD::ATOMIC_LOAD_MAX:
455 case ISD::ATOMIC_LOAD_UMIN:
456 case ISD::ATOMIC_LOAD_UMAX:
457 case ISD::ATOMIC_LOAD:
458 case ISD::ATOMIC_STORE: {
459 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
460 ID.AddInteger(AT->getMemoryVT().getRawBits());
461 ID.AddInteger(AT->getRawSubclassData());
462 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
465 case ISD::PREFETCH: {
466 const MemSDNode *PF = cast<MemSDNode>(N);
467 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
470 case ISD::VECTOR_SHUFFLE: {
471 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
472 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
474 ID.AddInteger(SVN->getMaskElt(i));
477 case ISD::TargetBlockAddress:
478 case ISD::BlockAddress: {
479 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
480 ID.AddPointer(BA->getBlockAddress());
481 ID.AddInteger(BA->getOffset());
482 ID.AddInteger(BA->getTargetFlags());
485 } // end switch (N->getOpcode())
487 // Target specific memory nodes could also have address spaces to check.
488 if (N->isTargetMemoryOpcode())
489 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
492 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
494 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
495 AddNodeIDOpcode(ID, N->getOpcode());
496 // Add the return value info.
497 AddNodeIDValueTypes(ID, N->getVTList());
498 // Add the operand info.
499 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
501 // Handle SDNode leafs with special info.
502 AddNodeIDCustom(ID, N);
505 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
506 /// the CSE map that carries volatility, temporalness, indexing mode, and
507 /// extension/truncation information.
509 static inline unsigned
510 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
511 bool isNonTemporal, bool isInvariant) {
512 assert((ConvType & 3) == ConvType &&
513 "ConvType may not require more than 2 bits!");
514 assert((AM & 7) == AM &&
515 "AM may not require more than 3 bits!");
519 (isNonTemporal << 6) |
523 //===----------------------------------------------------------------------===//
524 // SelectionDAG Class
525 //===----------------------------------------------------------------------===//
527 /// doNotCSE - Return true if CSE should not be performed for this node.
528 static bool doNotCSE(SDNode *N) {
529 if (N->getValueType(0) == MVT::Glue)
530 return true; // Never CSE anything that produces a flag.
532 switch (N->getOpcode()) {
534 case ISD::HANDLENODE:
536 return true; // Never CSE these nodes.
539 // Check that remaining values produced are not flags.
540 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
541 if (N->getValueType(i) == MVT::Glue)
542 return true; // Never CSE anything that produces a flag.
547 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
549 void SelectionDAG::RemoveDeadNodes() {
550 // Create a dummy node (which is not added to allnodes), that adds a reference
551 // to the root node, preventing it from being deleted.
552 HandleSDNode Dummy(getRoot());
554 SmallVector<SDNode*, 128> DeadNodes;
556 // Add all obviously-dead nodes to the DeadNodes worklist.
557 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
559 DeadNodes.push_back(I);
561 RemoveDeadNodes(DeadNodes);
563 // If the root changed (e.g. it was a dead load, update the root).
564 setRoot(Dummy.getValue());
567 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
568 /// given list, and any nodes that become unreachable as a result.
569 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
571 // Process the worklist, deleting the nodes and adding their uses to the
573 while (!DeadNodes.empty()) {
574 SDNode *N = DeadNodes.pop_back_val();
576 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
577 DUL->NodeDeleted(N, 0);
579 // Take the node out of the appropriate CSE map.
580 RemoveNodeFromCSEMaps(N);
582 // Next, brutally remove the operand list. This is safe to do, as there are
583 // no cycles in the graph.
584 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
586 SDNode *Operand = Use.getNode();
589 // Now that we removed this operand, see if there are no uses of it left.
590 if (Operand->use_empty())
591 DeadNodes.push_back(Operand);
598 void SelectionDAG::RemoveDeadNode(SDNode *N){
599 SmallVector<SDNode*, 16> DeadNodes(1, N);
601 // Create a dummy node that adds a reference to the root node, preventing
602 // it from being deleted. (This matters if the root is an operand of the
604 HandleSDNode Dummy(getRoot());
606 RemoveDeadNodes(DeadNodes);
609 void SelectionDAG::DeleteNode(SDNode *N) {
610 // First take this out of the appropriate CSE map.
611 RemoveNodeFromCSEMaps(N);
613 // Finally, remove uses due to operands of this node, remove from the
614 // AllNodes list, and delete the node.
615 DeleteNodeNotInCSEMaps(N);
618 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
619 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
620 assert(N->use_empty() && "Cannot delete a node that is not dead!");
622 // Drop all of the operands and decrement used node's use counts.
628 void SelectionDAG::DeallocateNode(SDNode *N) {
629 if (N->OperandsNeedDelete)
630 delete[] N->OperandList;
632 // Set the opcode to DELETED_NODE to help catch bugs when node
633 // memory is reallocated.
634 N->NodeType = ISD::DELETED_NODE;
636 NodeAllocator.Deallocate(AllNodes.remove(N));
638 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
639 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
640 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
641 DbgVals[i]->setIsInvalidated();
644 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
645 /// correspond to it. This is useful when we're about to delete or repurpose
646 /// the node. We don't want future request for structurally identical nodes
647 /// to return N anymore.
648 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
650 switch (N->getOpcode()) {
651 case ISD::HANDLENODE: return false; // noop.
653 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
654 "Cond code doesn't exist!");
655 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
656 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
658 case ISD::ExternalSymbol:
659 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
661 case ISD::TargetExternalSymbol: {
662 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
663 Erased = TargetExternalSymbols.erase(
664 std::pair<std::string,unsigned char>(ESN->getSymbol(),
665 ESN->getTargetFlags()));
668 case ISD::VALUETYPE: {
669 EVT VT = cast<VTSDNode>(N)->getVT();
670 if (VT.isExtended()) {
671 Erased = ExtendedValueTypeNodes.erase(VT);
673 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
674 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
679 // Remove it from the CSE Map.
680 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
681 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
682 Erased = CSEMap.RemoveNode(N);
686 // Verify that the node was actually in one of the CSE maps, unless it has a
687 // flag result (which cannot be CSE'd) or is one of the special cases that are
688 // not subject to CSE.
689 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
690 !N->isMachineOpcode() && !doNotCSE(N)) {
693 llvm_unreachable("Node is not in map!");
699 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
700 /// maps and modified in place. Add it back to the CSE maps, unless an identical
701 /// node already exists, in which case transfer all its users to the existing
702 /// node. This transfer can potentially trigger recursive merging.
705 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
706 // For node types that aren't CSE'd, just act as if no identical node
709 SDNode *Existing = CSEMap.GetOrInsertNode(N);
711 // If there was already an existing matching node, use ReplaceAllUsesWith
712 // to replace the dead one with the existing one. This can cause
713 // recursive merging of other unrelated nodes down the line.
714 ReplaceAllUsesWith(N, Existing);
716 // N is now dead. Inform the listeners and delete it.
717 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
718 DUL->NodeDeleted(N, Existing);
719 DeleteNodeNotInCSEMaps(N);
724 // If the node doesn't already exist, we updated it. Inform listeners.
725 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
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, SDValue Op,
738 SDValue Ops[] = { Op };
740 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
741 AddNodeIDCustom(ID, N);
742 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
746 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
747 /// were replaced with those specified. If this node is never memoized,
748 /// return null, otherwise return a pointer to the slot it would take. If a
749 /// node already exists with these operands, the slot will be non-null.
750 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
751 SDValue Op1, SDValue Op2,
756 SDValue Ops[] = { Op1, Op2 };
758 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
759 AddNodeIDCustom(ID, N);
760 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
765 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
766 /// were replaced with those specified. If this node is never memoized,
767 /// return null, otherwise return a pointer to the slot it would take. If a
768 /// node already exists with these operands, the slot will be non-null.
769 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
770 const SDValue *Ops,unsigned NumOps,
776 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
777 AddNodeIDCustom(ID, N);
778 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
783 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
784 static void VerifyNodeCommon(SDNode *N) {
785 switch (N->getOpcode()) {
788 case ISD::BUILD_PAIR: {
789 EVT VT = N->getValueType(0);
790 assert(N->getNumValues() == 1 && "Too many results!");
791 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
792 "Wrong return type!");
793 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
794 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
795 "Mismatched operand types!");
796 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
797 "Wrong operand type!");
798 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
799 "Wrong return type size");
802 case ISD::BUILD_VECTOR: {
803 assert(N->getNumValues() == 1 && "Too many results!");
804 assert(N->getValueType(0).isVector() && "Wrong return type!");
805 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
806 "Wrong number of operands!");
807 EVT EltVT = N->getValueType(0).getVectorElementType();
808 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
809 assert((I->getValueType() == EltVT ||
810 (EltVT.isInteger() && I->getValueType().isInteger() &&
811 EltVT.bitsLE(I->getValueType()))) &&
812 "Wrong operand type!");
813 assert(I->getValueType() == N->getOperand(0).getValueType() &&
814 "Operands must all have the same type");
821 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
822 static void VerifySDNode(SDNode *N) {
823 // The SDNode allocators cannot be used to allocate nodes with fields that are
824 // not present in an SDNode!
825 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
826 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
827 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
828 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
829 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
830 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
831 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
832 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
833 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
834 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
835 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
836 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
837 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
838 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
839 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
840 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
841 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
842 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
843 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
848 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
850 static void VerifyMachineNode(SDNode *N) {
851 // The MachineNode allocators cannot be used to allocate nodes with fields
852 // that are not present in a MachineNode!
853 // Currently there are no such nodes.
859 /// getEVTAlignment - Compute the default alignment value for the
862 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
863 Type *Ty = VT == MVT::iPTR ?
864 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
865 VT.getTypeForEVT(*getContext());
867 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
870 // EntryNode could meaningfully have debug info if we can find it...
871 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
872 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TTI(0), TLI(0), OptLevel(OL),
873 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
874 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
876 AllNodes.push_back(&EntryNode);
877 DbgInfo = new SDDbgInfo();
880 void SelectionDAG::init(MachineFunction &mf, const TargetTransformInfo *tti,
881 const TargetLowering *tli) {
885 Context = &mf.getFunction()->getContext();
888 SelectionDAG::~SelectionDAG() {
889 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
894 void SelectionDAG::allnodes_clear() {
895 assert(&*AllNodes.begin() == &EntryNode);
896 AllNodes.remove(AllNodes.begin());
897 while (!AllNodes.empty())
898 DeallocateNode(AllNodes.begin());
901 void SelectionDAG::clear() {
903 OperandAllocator.Reset();
906 ExtendedValueTypeNodes.clear();
907 ExternalSymbols.clear();
908 TargetExternalSymbols.clear();
909 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
910 static_cast<CondCodeSDNode*>(0));
911 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
912 static_cast<SDNode*>(0));
914 EntryNode.UseList = 0;
915 AllNodes.push_back(&EntryNode);
916 Root = getEntryNode();
920 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
921 return VT.bitsGT(Op.getValueType()) ?
922 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
923 getNode(ISD::TRUNCATE, DL, VT, Op);
926 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
927 return VT.bitsGT(Op.getValueType()) ?
928 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
929 getNode(ISD::TRUNCATE, DL, VT, Op);
932 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
933 return VT.bitsGT(Op.getValueType()) ?
934 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
935 getNode(ISD::TRUNCATE, DL, VT, Op);
938 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
939 assert(!VT.isVector() &&
940 "getZeroExtendInReg should use the vector element type instead of "
942 if (Op.getValueType() == VT) return Op;
943 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
944 APInt Imm = APInt::getLowBitsSet(BitWidth,
946 return getNode(ISD::AND, DL, Op.getValueType(), Op,
947 getConstant(Imm, Op.getValueType()));
950 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
952 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
953 EVT EltVT = VT.getScalarType();
955 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
956 return getNode(ISD::XOR, DL, VT, Val, NegOne);
959 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
960 EVT EltVT = VT.getScalarType();
961 assert((EltVT.getSizeInBits() >= 64 ||
962 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
963 "getConstant with a uint64_t value that doesn't fit in the type!");
964 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
967 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
968 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
971 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
972 assert(VT.isInteger() && "Cannot create FP integer constant!");
974 EVT EltVT = VT.getScalarType();
975 const ConstantInt *Elt = &Val;
977 const TargetLowering *TLI = TM.getTargetLowering();
979 // In some cases the vector type is legal but the element type is illegal and
980 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
981 // inserted value (the type does not need to match the vector element type).
982 // Any extra bits introduced will be truncated away.
983 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
984 TargetLowering::TypePromoteInteger) {
985 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
986 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
987 Elt = ConstantInt::get(*getContext(), NewVal);
989 // In other cases the element type is illegal and needs to be expanded, for
990 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
991 // the value into n parts and use a vector type with n-times the elements.
992 // Then bitcast to the type requested.
993 // Legalizing constants too early makes the DAGCombiner's job harder so we
994 // only legalize if the DAG tells us we must produce legal types.
995 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
996 TLI->getTypeAction(*getContext(), EltVT) ==
997 TargetLowering::TypeExpandInteger) {
998 APInt NewVal = Elt->getValue();
999 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1000 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1001 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1002 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1004 // Check the temporary vector is the correct size. If this fails then
1005 // getTypeToTransformTo() probably returned a type whose size (in bits)
1006 // isn't a power-of-2 factor of the requested type size.
1007 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1009 SmallVector<SDValue, 2> EltParts;
1010 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1011 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1012 .trunc(ViaEltSizeInBits),
1016 // EltParts is currently in little endian order. If we actually want
1017 // big-endian order then reverse it now.
1018 if (TLI->isBigEndian())
1019 std::reverse(EltParts.begin(), EltParts.end());
1021 // The elements must be reversed when the element order is different
1022 // to the endianness of the elements (because the BITCAST is itself a
1023 // vector shuffle in this situation). However, we do not need any code to
1024 // perform this reversal because getConstant() is producing a vector
1026 // This situation occurs in MIPS MSA.
1028 SmallVector<SDValue, 8> Ops;
1029 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1030 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1032 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1033 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1034 &Ops[0], Ops.size()));
1038 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1039 "APInt size does not match type size!");
1040 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1041 FoldingSetNodeID ID;
1042 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1046 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1048 return SDValue(N, 0);
1051 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1052 CSEMap.InsertNode(N, IP);
1053 AllNodes.push_back(N);
1056 SDValue Result(N, 0);
1057 if (VT.isVector()) {
1058 SmallVector<SDValue, 8> Ops;
1059 Ops.assign(VT.getVectorNumElements(), Result);
1060 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1065 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1066 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1070 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1071 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1074 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1075 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1077 EVT EltVT = VT.getScalarType();
1079 // Do the map lookup using the actual bit pattern for the floating point
1080 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1081 // we don't have issues with SNANs.
1082 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1083 FoldingSetNodeID ID;
1084 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1088 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1090 return SDValue(N, 0);
1093 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1094 CSEMap.InsertNode(N, IP);
1095 AllNodes.push_back(N);
1098 SDValue Result(N, 0);
1099 if (VT.isVector()) {
1100 SmallVector<SDValue, 8> Ops;
1101 Ops.assign(VT.getVectorNumElements(), Result);
1102 // FIXME SDLoc info might be appropriate here
1103 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1108 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1109 EVT EltVT = VT.getScalarType();
1110 if (EltVT==MVT::f32)
1111 return getConstantFP(APFloat((float)Val), VT, isTarget);
1112 else if (EltVT==MVT::f64)
1113 return getConstantFP(APFloat(Val), VT, isTarget);
1114 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1117 APFloat apf = APFloat(Val);
1118 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1120 return getConstantFP(apf, VT, isTarget);
1122 llvm_unreachable("Unsupported type in getConstantFP");
1125 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1126 EVT VT, int64_t Offset,
1128 unsigned char TargetFlags) {
1129 assert((TargetFlags == 0 || isTargetGA) &&
1130 "Cannot set target flags on target-independent globals");
1131 const TargetLowering *TLI = TM.getTargetLowering();
1133 // Truncate (with sign-extension) the offset value to the pointer size.
1134 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1136 Offset = SignExtend64(Offset, BitWidth);
1138 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1140 // If GV is an alias then use the aliasee for determining thread-localness.
1141 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1142 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1146 if (GVar && GVar->isThreadLocal())
1147 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1149 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1151 FoldingSetNodeID ID;
1152 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1154 ID.AddInteger(Offset);
1155 ID.AddInteger(TargetFlags);
1156 ID.AddInteger(GV->getType()->getAddressSpace());
1158 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1159 return SDValue(E, 0);
1161 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1162 DL.getDebugLoc(), GV, VT,
1163 Offset, TargetFlags);
1164 CSEMap.InsertNode(N, IP);
1165 AllNodes.push_back(N);
1166 return SDValue(N, 0);
1169 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1170 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1171 FoldingSetNodeID ID;
1172 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1175 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1176 return SDValue(E, 0);
1178 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1179 CSEMap.InsertNode(N, IP);
1180 AllNodes.push_back(N);
1181 return SDValue(N, 0);
1184 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1185 unsigned char TargetFlags) {
1186 assert((TargetFlags == 0 || isTarget) &&
1187 "Cannot set target flags on target-independent jump tables");
1188 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1189 FoldingSetNodeID ID;
1190 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1192 ID.AddInteger(TargetFlags);
1194 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1195 return SDValue(E, 0);
1197 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1199 CSEMap.InsertNode(N, IP);
1200 AllNodes.push_back(N);
1201 return SDValue(N, 0);
1204 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1205 unsigned Alignment, int Offset,
1207 unsigned char TargetFlags) {
1208 assert((TargetFlags == 0 || isTarget) &&
1209 "Cannot set target flags on target-independent globals");
1212 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1213 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1214 FoldingSetNodeID ID;
1215 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1216 ID.AddInteger(Alignment);
1217 ID.AddInteger(Offset);
1219 ID.AddInteger(TargetFlags);
1221 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1222 return SDValue(E, 0);
1224 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1225 Alignment, TargetFlags);
1226 CSEMap.InsertNode(N, IP);
1227 AllNodes.push_back(N);
1228 return SDValue(N, 0);
1232 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1233 unsigned Alignment, int Offset,
1235 unsigned char TargetFlags) {
1236 assert((TargetFlags == 0 || isTarget) &&
1237 "Cannot set target flags on target-independent globals");
1240 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1241 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1242 FoldingSetNodeID ID;
1243 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1244 ID.AddInteger(Alignment);
1245 ID.AddInteger(Offset);
1246 C->addSelectionDAGCSEId(ID);
1247 ID.AddInteger(TargetFlags);
1249 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1250 return SDValue(E, 0);
1252 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1253 Alignment, TargetFlags);
1254 CSEMap.InsertNode(N, IP);
1255 AllNodes.push_back(N);
1256 return SDValue(N, 0);
1259 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1260 unsigned char TargetFlags) {
1261 FoldingSetNodeID ID;
1262 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1263 ID.AddInteger(Index);
1264 ID.AddInteger(Offset);
1265 ID.AddInteger(TargetFlags);
1267 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268 return SDValue(E, 0);
1270 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1272 CSEMap.InsertNode(N, IP);
1273 AllNodes.push_back(N);
1274 return SDValue(N, 0);
1277 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1278 FoldingSetNodeID ID;
1279 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1282 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1283 return SDValue(E, 0);
1285 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1286 CSEMap.InsertNode(N, IP);
1287 AllNodes.push_back(N);
1288 return SDValue(N, 0);
1291 SDValue SelectionDAG::getValueType(EVT VT) {
1292 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1293 ValueTypeNodes.size())
1294 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1296 SDNode *&N = VT.isExtended() ?
1297 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1299 if (N) return SDValue(N, 0);
1300 N = new (NodeAllocator) VTSDNode(VT);
1301 AllNodes.push_back(N);
1302 return SDValue(N, 0);
1305 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1306 SDNode *&N = ExternalSymbols[Sym];
1307 if (N) return SDValue(N, 0);
1308 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1309 AllNodes.push_back(N);
1310 return SDValue(N, 0);
1313 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1314 unsigned char TargetFlags) {
1316 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1318 if (N) return SDValue(N, 0);
1319 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1320 AllNodes.push_back(N);
1321 return SDValue(N, 0);
1324 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1325 if ((unsigned)Cond >= CondCodeNodes.size())
1326 CondCodeNodes.resize(Cond+1);
1328 if (CondCodeNodes[Cond] == 0) {
1329 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1330 CondCodeNodes[Cond] = N;
1331 AllNodes.push_back(N);
1334 return SDValue(CondCodeNodes[Cond], 0);
1337 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1338 // the shuffle mask M that point at N1 to point at N2, and indices that point
1339 // N2 to point at N1.
1340 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1342 int NElts = M.size();
1343 for (int i = 0; i != NElts; ++i) {
1351 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1352 SDValue N2, const int *Mask) {
1353 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1354 "Invalid VECTOR_SHUFFLE");
1356 // Canonicalize shuffle undef, undef -> undef
1357 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1358 return getUNDEF(VT);
1360 // Validate that all indices in Mask are within the range of the elements
1361 // input to the shuffle.
1362 unsigned NElts = VT.getVectorNumElements();
1363 SmallVector<int, 8> MaskVec;
1364 for (unsigned i = 0; i != NElts; ++i) {
1365 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1366 MaskVec.push_back(Mask[i]);
1369 // Canonicalize shuffle v, v -> v, undef
1372 for (unsigned i = 0; i != NElts; ++i)
1373 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1376 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1377 if (N1.getOpcode() == ISD::UNDEF)
1378 commuteShuffle(N1, N2, MaskVec);
1380 // Canonicalize all index into lhs, -> shuffle lhs, undef
1381 // Canonicalize all index into rhs, -> shuffle rhs, undef
1382 bool AllLHS = true, AllRHS = true;
1383 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1384 for (unsigned i = 0; i != NElts; ++i) {
1385 if (MaskVec[i] >= (int)NElts) {
1390 } else if (MaskVec[i] >= 0) {
1394 if (AllLHS && AllRHS)
1395 return getUNDEF(VT);
1396 if (AllLHS && !N2Undef)
1400 commuteShuffle(N1, N2, MaskVec);
1403 // If Identity shuffle return that node.
1404 bool Identity = true;
1405 for (unsigned i = 0; i != NElts; ++i) {
1406 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1408 if (Identity && NElts)
1411 FoldingSetNodeID ID;
1412 SDValue Ops[2] = { N1, N2 };
1413 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1414 for (unsigned i = 0; i != NElts; ++i)
1415 ID.AddInteger(MaskVec[i]);
1418 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1419 return SDValue(E, 0);
1421 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1422 // SDNode doesn't have access to it. This memory will be "leaked" when
1423 // the node is deallocated, but recovered when the NodeAllocator is released.
1424 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1425 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1427 ShuffleVectorSDNode *N =
1428 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1429 dl.getDebugLoc(), N1, N2,
1431 CSEMap.InsertNode(N, IP);
1432 AllNodes.push_back(N);
1433 return SDValue(N, 0);
1436 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1437 SDValue Val, SDValue DTy,
1438 SDValue STy, SDValue Rnd, SDValue Sat,
1439 ISD::CvtCode Code) {
1440 // If the src and dest types are the same and the conversion is between
1441 // integer types of the same sign or two floats, no conversion is necessary.
1443 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1446 FoldingSetNodeID ID;
1447 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1448 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1450 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1451 return SDValue(E, 0);
1453 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1456 CSEMap.InsertNode(N, IP);
1457 AllNodes.push_back(N);
1458 return SDValue(N, 0);
1461 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1462 FoldingSetNodeID ID;
1463 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1464 ID.AddInteger(RegNo);
1466 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1467 return SDValue(E, 0);
1469 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1470 CSEMap.InsertNode(N, IP);
1471 AllNodes.push_back(N);
1472 return SDValue(N, 0);
1475 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1476 FoldingSetNodeID ID;
1477 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1478 ID.AddPointer(RegMask);
1480 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1481 return SDValue(E, 0);
1483 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1484 CSEMap.InsertNode(N, IP);
1485 AllNodes.push_back(N);
1486 return SDValue(N, 0);
1489 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1490 FoldingSetNodeID ID;
1491 SDValue Ops[] = { Root };
1492 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1493 ID.AddPointer(Label);
1495 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1496 return SDValue(E, 0);
1498 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1499 dl.getDebugLoc(), Root, Label);
1500 CSEMap.InsertNode(N, IP);
1501 AllNodes.push_back(N);
1502 return SDValue(N, 0);
1506 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1509 unsigned char TargetFlags) {
1510 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1512 FoldingSetNodeID ID;
1513 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1515 ID.AddInteger(Offset);
1516 ID.AddInteger(TargetFlags);
1518 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1519 return SDValue(E, 0);
1521 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1523 CSEMap.InsertNode(N, IP);
1524 AllNodes.push_back(N);
1525 return SDValue(N, 0);
1528 SDValue SelectionDAG::getSrcValue(const Value *V) {
1529 assert((!V || V->getType()->isPointerTy()) &&
1530 "SrcValue is not a pointer?");
1532 FoldingSetNodeID ID;
1533 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1537 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1538 return SDValue(E, 0);
1540 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1541 CSEMap.InsertNode(N, IP);
1542 AllNodes.push_back(N);
1543 return SDValue(N, 0);
1546 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1547 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1548 FoldingSetNodeID ID;
1549 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1553 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1554 return SDValue(E, 0);
1556 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1557 CSEMap.InsertNode(N, IP);
1558 AllNodes.push_back(N);
1559 return SDValue(N, 0);
1562 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1563 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1564 unsigned SrcAS, unsigned DestAS) {
1565 SDValue Ops[] = {Ptr};
1566 FoldingSetNodeID ID;
1567 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), &Ops[0], 1);
1568 ID.AddInteger(SrcAS);
1569 ID.AddInteger(DestAS);
1572 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1573 return SDValue(E, 0);
1575 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1577 VT, Ptr, SrcAS, DestAS);
1578 CSEMap.InsertNode(N, IP);
1579 AllNodes.push_back(N);
1580 return SDValue(N, 0);
1583 /// getShiftAmountOperand - Return the specified value casted to
1584 /// the target's desired shift amount type.
1585 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1586 EVT OpTy = Op.getValueType();
1587 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1588 if (OpTy == ShTy || OpTy.isVector()) return Op;
1590 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1591 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1594 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1595 /// specified value type.
1596 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1597 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1598 unsigned ByteSize = VT.getStoreSize();
1599 Type *Ty = VT.getTypeForEVT(*getContext());
1600 const TargetLowering *TLI = TM.getTargetLowering();
1601 unsigned StackAlign =
1602 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1604 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1605 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1608 /// CreateStackTemporary - Create a stack temporary suitable for holding
1609 /// either of the specified value types.
1610 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1611 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1612 VT2.getStoreSizeInBits())/8;
1613 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1614 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1615 const TargetLowering *TLI = TM.getTargetLowering();
1616 const DataLayout *TD = TLI->getDataLayout();
1617 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1618 TD->getPrefTypeAlignment(Ty2));
1620 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1621 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1622 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1625 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1626 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1627 // These setcc operations always fold.
1631 case ISD::SETFALSE2: return getConstant(0, VT);
1633 case ISD::SETTRUE2: {
1634 const TargetLowering *TLI = TM.getTargetLowering();
1635 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1637 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1650 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1654 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1655 const APInt &C2 = N2C->getAPIntValue();
1656 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1657 const APInt &C1 = N1C->getAPIntValue();
1660 default: llvm_unreachable("Unknown integer setcc!");
1661 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1662 case ISD::SETNE: return getConstant(C1 != C2, VT);
1663 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1664 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1665 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1666 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1667 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1668 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1669 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1670 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1674 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1675 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1676 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1679 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1680 return getUNDEF(VT);
1682 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1683 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1684 return getUNDEF(VT);
1686 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1687 R==APFloat::cmpLessThan, VT);
1688 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1689 return getUNDEF(VT);
1691 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1692 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1693 return getUNDEF(VT);
1695 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1696 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1697 return getUNDEF(VT);
1699 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1700 R==APFloat::cmpEqual, VT);
1701 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1702 return getUNDEF(VT);
1704 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1705 R==APFloat::cmpEqual, VT);
1706 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1707 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1708 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1709 R==APFloat::cmpEqual, VT);
1710 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1711 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1712 R==APFloat::cmpLessThan, VT);
1713 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1714 R==APFloat::cmpUnordered, VT);
1715 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1716 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1719 // Ensure that the constant occurs on the RHS.
1720 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1721 MVT CompVT = N1.getValueType().getSimpleVT();
1722 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1725 return getSetCC(dl, VT, N2, N1, SwappedCond);
1729 // Could not fold it.
1733 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1734 /// use this predicate to simplify operations downstream.
1735 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1736 // This predicate is not safe for vector operations.
1737 if (Op.getValueType().isVector())
1740 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1741 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1744 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1745 /// this predicate to simplify operations downstream. Mask is known to be zero
1746 /// for bits that V cannot have.
1747 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1748 unsigned Depth) const {
1749 APInt KnownZero, KnownOne;
1750 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1751 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1752 return (KnownZero & Mask) == Mask;
1755 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1756 /// known to be either zero or one and return them in the KnownZero/KnownOne
1757 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1759 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1760 APInt &KnownOne, unsigned Depth) const {
1761 const TargetLowering *TLI = TM.getTargetLowering();
1762 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1764 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1766 return; // Limit search depth.
1768 APInt KnownZero2, KnownOne2;
1770 switch (Op.getOpcode()) {
1772 // We know all of the bits for a constant!
1773 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1774 KnownZero = ~KnownOne;
1777 // If either the LHS or the RHS are Zero, the result is zero.
1778 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1779 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1780 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1781 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1783 // Output known-1 bits are only known if set in both the LHS & RHS.
1784 KnownOne &= KnownOne2;
1785 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1786 KnownZero |= KnownZero2;
1789 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1790 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1791 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1792 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1794 // Output known-0 bits are only known if clear in both the LHS & RHS.
1795 KnownZero &= KnownZero2;
1796 // Output known-1 are known to be set if set in either the LHS | RHS.
1797 KnownOne |= KnownOne2;
1800 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1801 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1802 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1803 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1805 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1806 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1807 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1808 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1809 KnownZero = KnownZeroOut;
1813 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1814 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1815 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1816 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1818 // If low bits are zero in either operand, output low known-0 bits.
1819 // Also compute a conserative estimate for high known-0 bits.
1820 // More trickiness is possible, but this is sufficient for the
1821 // interesting case of alignment computation.
1822 KnownOne.clearAllBits();
1823 unsigned TrailZ = KnownZero.countTrailingOnes() +
1824 KnownZero2.countTrailingOnes();
1825 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1826 KnownZero2.countLeadingOnes(),
1827 BitWidth) - BitWidth;
1829 TrailZ = std::min(TrailZ, BitWidth);
1830 LeadZ = std::min(LeadZ, BitWidth);
1831 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1832 APInt::getHighBitsSet(BitWidth, LeadZ);
1836 // For the purposes of computing leading zeros we can conservatively
1837 // treat a udiv as a logical right shift by the power of 2 known to
1838 // be less than the denominator.
1839 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1840 unsigned LeadZ = KnownZero2.countLeadingOnes();
1842 KnownOne2.clearAllBits();
1843 KnownZero2.clearAllBits();
1844 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1845 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1846 if (RHSUnknownLeadingOnes != BitWidth)
1847 LeadZ = std::min(BitWidth,
1848 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1850 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1854 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1855 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1856 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1857 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1859 // Only known if known in both the LHS and RHS.
1860 KnownOne &= KnownOne2;
1861 KnownZero &= KnownZero2;
1863 case ISD::SELECT_CC:
1864 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1865 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1866 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1867 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1869 // Only known if known in both the LHS and RHS.
1870 KnownOne &= KnownOne2;
1871 KnownZero &= KnownZero2;
1879 if (Op.getResNo() != 1)
1881 // The boolean result conforms to getBooleanContents. Fall through.
1883 // If we know the result of a setcc has the top bits zero, use this info.
1884 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1885 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1886 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1889 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1890 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1891 unsigned ShAmt = SA->getZExtValue();
1893 // If the shift count is an invalid immediate, don't do anything.
1894 if (ShAmt >= BitWidth)
1897 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1898 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1899 KnownZero <<= ShAmt;
1901 // low bits known zero.
1902 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1906 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1907 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1908 unsigned ShAmt = SA->getZExtValue();
1910 // If the shift count is an invalid immediate, don't do anything.
1911 if (ShAmt >= BitWidth)
1914 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1915 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1916 KnownZero = KnownZero.lshr(ShAmt);
1917 KnownOne = KnownOne.lshr(ShAmt);
1919 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1920 KnownZero |= HighBits; // High bits known zero.
1924 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1925 unsigned ShAmt = SA->getZExtValue();
1927 // If the shift count is an invalid immediate, don't do anything.
1928 if (ShAmt >= BitWidth)
1931 // If any of the demanded bits are produced by the sign extension, we also
1932 // demand the input sign bit.
1933 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1935 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1936 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1937 KnownZero = KnownZero.lshr(ShAmt);
1938 KnownOne = KnownOne.lshr(ShAmt);
1940 // Handle the sign bits.
1941 APInt SignBit = APInt::getSignBit(BitWidth);
1942 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1944 if (KnownZero.intersects(SignBit)) {
1945 KnownZero |= HighBits; // New bits are known zero.
1946 } else if (KnownOne.intersects(SignBit)) {
1947 KnownOne |= HighBits; // New bits are known one.
1951 case ISD::SIGN_EXTEND_INREG: {
1952 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1953 unsigned EBits = EVT.getScalarType().getSizeInBits();
1955 // Sign extension. Compute the demanded bits in the result that are not
1956 // present in the input.
1957 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1959 APInt InSignBit = APInt::getSignBit(EBits);
1960 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1962 // If the sign extended bits are demanded, we know that the sign
1964 InSignBit = InSignBit.zext(BitWidth);
1965 if (NewBits.getBoolValue())
1966 InputDemandedBits |= InSignBit;
1968 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1969 KnownOne &= InputDemandedBits;
1970 KnownZero &= InputDemandedBits;
1971 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1973 // If the sign bit of the input is known set or clear, then we know the
1974 // top bits of the result.
1975 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1976 KnownZero |= NewBits;
1977 KnownOne &= ~NewBits;
1978 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1979 KnownOne |= NewBits;
1980 KnownZero &= ~NewBits;
1981 } else { // Input sign bit unknown
1982 KnownZero &= ~NewBits;
1983 KnownOne &= ~NewBits;
1988 case ISD::CTTZ_ZERO_UNDEF:
1990 case ISD::CTLZ_ZERO_UNDEF:
1992 unsigned LowBits = Log2_32(BitWidth)+1;
1993 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1994 KnownOne.clearAllBits();
1998 LoadSDNode *LD = cast<LoadSDNode>(Op);
1999 // If this is a ZEXTLoad and we are looking at the loaded value.
2000 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2001 EVT VT = LD->getMemoryVT();
2002 unsigned MemBits = VT.getScalarType().getSizeInBits();
2003 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2004 } else if (const MDNode *Ranges = LD->getRanges()) {
2005 computeMaskedBitsLoad(*Ranges, KnownZero);
2009 case ISD::ZERO_EXTEND: {
2010 EVT InVT = Op.getOperand(0).getValueType();
2011 unsigned InBits = InVT.getScalarType().getSizeInBits();
2012 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2013 KnownZero = KnownZero.trunc(InBits);
2014 KnownOne = KnownOne.trunc(InBits);
2015 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2016 KnownZero = KnownZero.zext(BitWidth);
2017 KnownOne = KnownOne.zext(BitWidth);
2018 KnownZero |= NewBits;
2021 case ISD::SIGN_EXTEND: {
2022 EVT InVT = Op.getOperand(0).getValueType();
2023 unsigned InBits = InVT.getScalarType().getSizeInBits();
2024 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2026 KnownZero = KnownZero.trunc(InBits);
2027 KnownOne = KnownOne.trunc(InBits);
2028 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2030 // Note if the sign bit is known to be zero or one.
2031 bool SignBitKnownZero = KnownZero.isNegative();
2032 bool SignBitKnownOne = KnownOne.isNegative();
2033 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2034 "Sign bit can't be known to be both zero and one!");
2036 KnownZero = KnownZero.zext(BitWidth);
2037 KnownOne = KnownOne.zext(BitWidth);
2039 // If the sign bit is known zero or one, the top bits match.
2040 if (SignBitKnownZero)
2041 KnownZero |= NewBits;
2042 else if (SignBitKnownOne)
2043 KnownOne |= NewBits;
2046 case ISD::ANY_EXTEND: {
2047 EVT InVT = Op.getOperand(0).getValueType();
2048 unsigned InBits = InVT.getScalarType().getSizeInBits();
2049 KnownZero = KnownZero.trunc(InBits);
2050 KnownOne = KnownOne.trunc(InBits);
2051 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2052 KnownZero = KnownZero.zext(BitWidth);
2053 KnownOne = KnownOne.zext(BitWidth);
2056 case ISD::TRUNCATE: {
2057 EVT InVT = Op.getOperand(0).getValueType();
2058 unsigned InBits = InVT.getScalarType().getSizeInBits();
2059 KnownZero = KnownZero.zext(InBits);
2060 KnownOne = KnownOne.zext(InBits);
2061 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2062 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2063 KnownZero = KnownZero.trunc(BitWidth);
2064 KnownOne = KnownOne.trunc(BitWidth);
2067 case ISD::AssertZext: {
2068 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2069 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2070 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2071 KnownZero |= (~InMask);
2072 KnownOne &= (~KnownZero);
2076 // All bits are zero except the low bit.
2077 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2081 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2082 // We know that the top bits of C-X are clear if X contains less bits
2083 // than C (i.e. no wrap-around can happen). For example, 20-X is
2084 // positive if we can prove that X is >= 0 and < 16.
2085 if (CLHS->getAPIntValue().isNonNegative()) {
2086 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2087 // NLZ can't be BitWidth with no sign bit
2088 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2089 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2091 // If all of the MaskV bits are known to be zero, then we know the
2092 // output top bits are zero, because we now know that the output is
2094 if ((KnownZero2 & MaskV) == MaskV) {
2095 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2096 // Top bits known zero.
2097 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2105 // Output known-0 bits are known if clear or set in both the low clear bits
2106 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2107 // low 3 bits clear.
2108 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2109 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2110 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2112 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2113 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2114 KnownZeroOut = std::min(KnownZeroOut,
2115 KnownZero2.countTrailingOnes());
2117 if (Op.getOpcode() == ISD::ADD) {
2118 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2122 // With ADDE, a carry bit may be added in, so we can only use this
2123 // information if we know (at least) that the low two bits are clear. We
2124 // then return to the caller that the low bit is unknown but that other bits
2126 if (KnownZeroOut >= 2) // ADDE
2127 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2131 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2132 const APInt &RA = Rem->getAPIntValue().abs();
2133 if (RA.isPowerOf2()) {
2134 APInt LowBits = RA - 1;
2135 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2137 // The low bits of the first operand are unchanged by the srem.
2138 KnownZero = KnownZero2 & LowBits;
2139 KnownOne = KnownOne2 & LowBits;
2141 // If the first operand is non-negative or has all low bits zero, then
2142 // the upper bits are all zero.
2143 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2144 KnownZero |= ~LowBits;
2146 // If the first operand is negative and not all low bits are zero, then
2147 // the upper bits are all one.
2148 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2149 KnownOne |= ~LowBits;
2150 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2155 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2156 const APInt &RA = Rem->getAPIntValue();
2157 if (RA.isPowerOf2()) {
2158 APInt LowBits = (RA - 1);
2159 KnownZero |= ~LowBits;
2160 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2161 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2166 // Since the result is less than or equal to either operand, any leading
2167 // zero bits in either operand must also exist in the result.
2168 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2169 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2171 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2172 KnownZero2.countLeadingOnes());
2173 KnownOne.clearAllBits();
2174 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2177 case ISD::FrameIndex:
2178 case ISD::TargetFrameIndex:
2179 if (unsigned Align = InferPtrAlignment(Op)) {
2180 // The low bits are known zero if the pointer is aligned.
2181 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2187 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2190 case ISD::INTRINSIC_WO_CHAIN:
2191 case ISD::INTRINSIC_W_CHAIN:
2192 case ISD::INTRINSIC_VOID:
2193 // Allow the target to implement this method for its nodes.
2194 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2199 /// ComputeNumSignBits - Return the number of times the sign bit of the
2200 /// register is replicated into the other bits. We know that at least 1 bit
2201 /// is always equal to the sign bit (itself), but other cases can give us
2202 /// information. For example, immediately after an "SRA X, 2", we know that
2203 /// the top 3 bits are all equal to each other, so we return 3.
2204 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2205 const TargetLowering *TLI = TM.getTargetLowering();
2206 EVT VT = Op.getValueType();
2207 assert(VT.isInteger() && "Invalid VT!");
2208 unsigned VTBits = VT.getScalarType().getSizeInBits();
2210 unsigned FirstAnswer = 1;
2213 return 1; // Limit search depth.
2215 switch (Op.getOpcode()) {
2217 case ISD::AssertSext:
2218 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2219 return VTBits-Tmp+1;
2220 case ISD::AssertZext:
2221 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2224 case ISD::Constant: {
2225 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2226 return Val.getNumSignBits();
2229 case ISD::SIGN_EXTEND:
2231 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2232 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2234 case ISD::SIGN_EXTEND_INREG:
2235 // Max of the input and what this extends.
2237 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2240 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2241 return std::max(Tmp, Tmp2);
2244 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2245 // SRA X, C -> adds C sign bits.
2246 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2247 Tmp += C->getZExtValue();
2248 if (Tmp > VTBits) Tmp = VTBits;
2252 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2253 // shl destroys sign bits.
2254 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2255 if (C->getZExtValue() >= VTBits || // Bad shift.
2256 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2257 return Tmp - C->getZExtValue();
2262 case ISD::XOR: // NOT is handled here.
2263 // Logical binary ops preserve the number of sign bits at the worst.
2264 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2266 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2267 FirstAnswer = std::min(Tmp, Tmp2);
2268 // We computed what we know about the sign bits as our first
2269 // answer. Now proceed to the generic code that uses
2270 // ComputeMaskedBits, and pick whichever answer is better.
2275 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2276 if (Tmp == 1) return 1; // Early out.
2277 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2278 return std::min(Tmp, Tmp2);
2286 if (Op.getResNo() != 1)
2288 // The boolean result conforms to getBooleanContents. Fall through.
2290 // If setcc returns 0/-1, all bits are sign bits.
2291 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2292 TargetLowering::ZeroOrNegativeOneBooleanContent)
2297 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2298 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2300 // Handle rotate right by N like a rotate left by 32-N.
2301 if (Op.getOpcode() == ISD::ROTR)
2302 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2304 // If we aren't rotating out all of the known-in sign bits, return the
2305 // number that are left. This handles rotl(sext(x), 1) for example.
2306 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2307 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2311 // Add can have at most one carry bit. Thus we know that the output
2312 // is, at worst, one more bit than the inputs.
2313 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2314 if (Tmp == 1) return 1; // Early out.
2316 // Special case decrementing a value (ADD X, -1):
2317 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2318 if (CRHS->isAllOnesValue()) {
2319 APInt KnownZero, KnownOne;
2320 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2322 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2324 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2327 // If we are subtracting one from a positive number, there is no carry
2328 // out of the result.
2329 if (KnownZero.isNegative())
2333 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2334 if (Tmp2 == 1) return 1;
2335 return std::min(Tmp, Tmp2)-1;
2338 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2339 if (Tmp2 == 1) return 1;
2342 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2343 if (CLHS->isNullValue()) {
2344 APInt KnownZero, KnownOne;
2345 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2346 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2348 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2351 // If the input is known to be positive (the sign bit is known clear),
2352 // the output of the NEG has the same number of sign bits as the input.
2353 if (KnownZero.isNegative())
2356 // Otherwise, we treat this like a SUB.
2359 // Sub can have at most one carry bit. Thus we know that the output
2360 // is, at worst, one more bit than the inputs.
2361 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2362 if (Tmp == 1) return 1; // Early out.
2363 return std::min(Tmp, Tmp2)-1;
2365 // FIXME: it's tricky to do anything useful for this, but it is an important
2366 // case for targets like X86.
2370 // If we are looking at the loaded value of the SDNode.
2371 if (Op.getResNo() == 0) {
2372 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2373 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2374 unsigned ExtType = LD->getExtensionType();
2377 case ISD::SEXTLOAD: // '17' bits known
2378 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2379 return VTBits-Tmp+1;
2380 case ISD::ZEXTLOAD: // '16' bits known
2381 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2387 // Allow the target to implement this method for its nodes.
2388 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2389 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2390 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2391 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2392 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, Depth);
2393 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2396 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2397 // use this information.
2398 APInt KnownZero, KnownOne;
2399 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2402 if (KnownZero.isNegative()) { // sign bit is 0
2404 } else if (KnownOne.isNegative()) { // sign bit is 1;
2411 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2412 // the number of identical bits in the top of the input value.
2414 Mask <<= Mask.getBitWidth()-VTBits;
2415 // Return # leading zeros. We use 'min' here in case Val was zero before
2416 // shifting. We don't want to return '64' as for an i32 "0".
2417 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2420 /// isBaseWithConstantOffset - Return true if the specified operand is an
2421 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2422 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2423 /// semantics as an ADD. This handles the equivalence:
2424 /// X|Cst == X+Cst iff X&Cst = 0.
2425 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2426 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2427 !isa<ConstantSDNode>(Op.getOperand(1)))
2430 if (Op.getOpcode() == ISD::OR &&
2431 !MaskedValueIsZero(Op.getOperand(0),
2432 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2439 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2440 // If we're told that NaNs won't happen, assume they won't.
2441 if (getTarget().Options.NoNaNsFPMath)
2444 // If the value is a constant, we can obviously see if it is a NaN or not.
2445 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2446 return !C->getValueAPF().isNaN();
2448 // TODO: Recognize more cases here.
2453 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2454 // If the value is a constant, we can obviously see if it is a zero or not.
2455 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2456 return !C->isZero();
2458 // TODO: Recognize more cases here.
2459 switch (Op.getOpcode()) {
2462 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2463 return !C->isNullValue();
2470 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2471 // Check the obvious case.
2472 if (A == B) return true;
2474 // For for negative and positive zero.
2475 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2476 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2477 if (CA->isZero() && CB->isZero()) return true;
2479 // Otherwise they may not be equal.
2483 /// getNode - Gets or creates the specified node.
2485 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2486 FoldingSetNodeID ID;
2487 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2489 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2490 return SDValue(E, 0);
2492 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2493 DL.getDebugLoc(), getVTList(VT));
2494 CSEMap.InsertNode(N, IP);
2496 AllNodes.push_back(N);
2500 return SDValue(N, 0);
2503 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2504 EVT VT, SDValue Operand) {
2505 // Constant fold unary operations with an integer constant operand.
2506 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2507 const APInt &Val = C->getAPIntValue();
2510 case ISD::SIGN_EXTEND:
2511 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2512 case ISD::ANY_EXTEND:
2513 case ISD::ZERO_EXTEND:
2515 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2516 case ISD::UINT_TO_FP:
2517 case ISD::SINT_TO_FP: {
2518 APFloat apf(EVTToAPFloatSemantics(VT),
2519 APInt::getNullValue(VT.getSizeInBits()));
2520 (void)apf.convertFromAPInt(Val,
2521 Opcode==ISD::SINT_TO_FP,
2522 APFloat::rmNearestTiesToEven);
2523 return getConstantFP(apf, VT);
2526 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2527 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2528 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2529 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2532 return getConstant(Val.byteSwap(), VT);
2534 return getConstant(Val.countPopulation(), VT);
2536 case ISD::CTLZ_ZERO_UNDEF:
2537 return getConstant(Val.countLeadingZeros(), VT);
2539 case ISD::CTTZ_ZERO_UNDEF:
2540 return getConstant(Val.countTrailingZeros(), VT);
2544 // Constant fold unary operations with a floating point constant operand.
2545 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2546 APFloat V = C->getValueAPF(); // make copy
2550 return getConstantFP(V, VT);
2553 return getConstantFP(V, VT);
2555 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2556 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2557 return getConstantFP(V, VT);
2561 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2562 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2563 return getConstantFP(V, VT);
2567 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2568 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2569 return getConstantFP(V, VT);
2572 case ISD::FP_EXTEND: {
2574 // This can return overflow, underflow, or inexact; we don't care.
2575 // FIXME need to be more flexible about rounding mode.
2576 (void)V.convert(EVTToAPFloatSemantics(VT),
2577 APFloat::rmNearestTiesToEven, &ignored);
2578 return getConstantFP(V, VT);
2580 case ISD::FP_TO_SINT:
2581 case ISD::FP_TO_UINT: {
2584 assert(integerPartWidth >= 64);
2585 // FIXME need to be more flexible about rounding mode.
2586 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2587 Opcode==ISD::FP_TO_SINT,
2588 APFloat::rmTowardZero, &ignored);
2589 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2591 APInt api(VT.getSizeInBits(), x);
2592 return getConstant(api, VT);
2595 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2596 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2597 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2598 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2603 unsigned OpOpcode = Operand.getNode()->getOpcode();
2605 case ISD::TokenFactor:
2606 case ISD::MERGE_VALUES:
2607 case ISD::CONCAT_VECTORS:
2608 return Operand; // Factor, merge or concat of one node? No need.
2609 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2610 case ISD::FP_EXTEND:
2611 assert(VT.isFloatingPoint() &&
2612 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2613 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2614 assert((!VT.isVector() ||
2615 VT.getVectorNumElements() ==
2616 Operand.getValueType().getVectorNumElements()) &&
2617 "Vector element count mismatch!");
2618 if (Operand.getOpcode() == ISD::UNDEF)
2619 return getUNDEF(VT);
2621 case ISD::SIGN_EXTEND:
2622 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2623 "Invalid SIGN_EXTEND!");
2624 if (Operand.getValueType() == VT) return Operand; // noop extension
2625 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2626 "Invalid sext node, dst < src!");
2627 assert((!VT.isVector() ||
2628 VT.getVectorNumElements() ==
2629 Operand.getValueType().getVectorNumElements()) &&
2630 "Vector element count mismatch!");
2631 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2632 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2633 else if (OpOpcode == ISD::UNDEF)
2634 // sext(undef) = 0, because the top bits will all be the same.
2635 return getConstant(0, VT);
2637 case ISD::ZERO_EXTEND:
2638 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2639 "Invalid ZERO_EXTEND!");
2640 if (Operand.getValueType() == VT) return Operand; // noop extension
2641 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2642 "Invalid zext node, dst < src!");
2643 assert((!VT.isVector() ||
2644 VT.getVectorNumElements() ==
2645 Operand.getValueType().getVectorNumElements()) &&
2646 "Vector element count mismatch!");
2647 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2648 return getNode(ISD::ZERO_EXTEND, DL, VT,
2649 Operand.getNode()->getOperand(0));
2650 else if (OpOpcode == ISD::UNDEF)
2651 // zext(undef) = 0, because the top bits will be zero.
2652 return getConstant(0, VT);
2654 case ISD::ANY_EXTEND:
2655 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2656 "Invalid ANY_EXTEND!");
2657 if (Operand.getValueType() == VT) return Operand; // noop extension
2658 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2659 "Invalid anyext node, dst < src!");
2660 assert((!VT.isVector() ||
2661 VT.getVectorNumElements() ==
2662 Operand.getValueType().getVectorNumElements()) &&
2663 "Vector element count mismatch!");
2665 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2666 OpOpcode == ISD::ANY_EXTEND)
2667 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2668 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2669 else if (OpOpcode == ISD::UNDEF)
2670 return getUNDEF(VT);
2672 // (ext (trunx x)) -> x
2673 if (OpOpcode == ISD::TRUNCATE) {
2674 SDValue OpOp = Operand.getNode()->getOperand(0);
2675 if (OpOp.getValueType() == VT)
2680 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2681 "Invalid TRUNCATE!");
2682 if (Operand.getValueType() == VT) return Operand; // noop truncate
2683 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2684 "Invalid truncate node, src < dst!");
2685 assert((!VT.isVector() ||
2686 VT.getVectorNumElements() ==
2687 Operand.getValueType().getVectorNumElements()) &&
2688 "Vector element count mismatch!");
2689 if (OpOpcode == ISD::TRUNCATE)
2690 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2691 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2692 OpOpcode == ISD::ANY_EXTEND) {
2693 // If the source is smaller than the dest, we still need an extend.
2694 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2695 .bitsLT(VT.getScalarType()))
2696 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2697 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2698 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2699 return Operand.getNode()->getOperand(0);
2701 if (OpOpcode == ISD::UNDEF)
2702 return getUNDEF(VT);
2705 // Basic sanity checking.
2706 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2707 && "Cannot BITCAST between types of different sizes!");
2708 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2709 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2710 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2711 if (OpOpcode == ISD::UNDEF)
2712 return getUNDEF(VT);
2714 case ISD::SCALAR_TO_VECTOR:
2715 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2716 (VT.getVectorElementType() == Operand.getValueType() ||
2717 (VT.getVectorElementType().isInteger() &&
2718 Operand.getValueType().isInteger() &&
2719 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2720 "Illegal SCALAR_TO_VECTOR node!");
2721 if (OpOpcode == ISD::UNDEF)
2722 return getUNDEF(VT);
2723 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2724 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2725 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2726 Operand.getConstantOperandVal(1) == 0 &&
2727 Operand.getOperand(0).getValueType() == VT)
2728 return Operand.getOperand(0);
2731 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2732 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2733 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2734 Operand.getNode()->getOperand(0));
2735 if (OpOpcode == ISD::FNEG) // --X -> X
2736 return Operand.getNode()->getOperand(0);
2739 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2740 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2745 SDVTList VTs = getVTList(VT);
2746 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2747 FoldingSetNodeID ID;
2748 SDValue Ops[1] = { Operand };
2749 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2751 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2752 return SDValue(E, 0);
2754 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2755 DL.getDebugLoc(), VTs, Operand);
2756 CSEMap.InsertNode(N, IP);
2758 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2759 DL.getDebugLoc(), VTs, Operand);
2762 AllNodes.push_back(N);
2766 return SDValue(N, 0);
2769 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2770 SDNode *Cst1, SDNode *Cst2) {
2771 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2772 SmallVector<SDValue, 4> Outputs;
2773 EVT SVT = VT.getScalarType();
2775 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2776 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2777 if (Scalar1 && Scalar2) {
2778 // Scalar instruction.
2779 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2781 // For vectors extract each constant element into Inputs so we can constant
2782 // fold them individually.
2783 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2784 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2788 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2790 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2791 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2792 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2793 if (!V1 || !V2) // Not a constant, bail.
2796 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2797 // FIXME: This is valid and could be handled by truncating the APInts.
2798 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2801 Inputs.push_back(std::make_pair(V1, V2));
2805 // We have a number of constant values, constant fold them element by element.
2806 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2807 const APInt &C1 = Inputs[I].first->getAPIntValue();
2808 const APInt &C2 = Inputs[I].second->getAPIntValue();
2812 Outputs.push_back(getConstant(C1 + C2, SVT));
2815 Outputs.push_back(getConstant(C1 - C2, SVT));
2818 Outputs.push_back(getConstant(C1 * C2, SVT));
2821 if (!C2.getBoolValue())
2823 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2826 if (!C2.getBoolValue())
2828 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2831 if (!C2.getBoolValue())
2833 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2836 if (!C2.getBoolValue())
2838 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2841 Outputs.push_back(getConstant(C1 & C2, SVT));
2844 Outputs.push_back(getConstant(C1 | C2, SVT));
2847 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2850 Outputs.push_back(getConstant(C1 << C2, SVT));
2853 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2856 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2859 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2862 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2869 // Handle the scalar case first.
2870 if (Scalar1 && Scalar2)
2871 return Outputs.back();
2873 // Otherwise build a big vector out of the scalar elements we generated.
2874 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs.data(),
2878 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2880 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2881 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2884 case ISD::TokenFactor:
2885 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2886 N2.getValueType() == MVT::Other && "Invalid token factor!");
2887 // Fold trivial token factors.
2888 if (N1.getOpcode() == ISD::EntryToken) return N2;
2889 if (N2.getOpcode() == ISD::EntryToken) return N1;
2890 if (N1 == N2) return N1;
2892 case ISD::CONCAT_VECTORS:
2893 // Concat of UNDEFs is UNDEF.
2894 if (N1.getOpcode() == ISD::UNDEF &&
2895 N2.getOpcode() == ISD::UNDEF)
2896 return getUNDEF(VT);
2898 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2899 // one big BUILD_VECTOR.
2900 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2901 N2.getOpcode() == ISD::BUILD_VECTOR) {
2902 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2903 N1.getNode()->op_end());
2904 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2905 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2909 assert(VT.isInteger() && "This operator does not apply to FP types!");
2910 assert(N1.getValueType() == N2.getValueType() &&
2911 N1.getValueType() == VT && "Binary operator types must match!");
2912 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2913 // worth handling here.
2914 if (N2C && N2C->isNullValue())
2916 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2923 assert(VT.isInteger() && "This operator does not apply to FP types!");
2924 assert(N1.getValueType() == N2.getValueType() &&
2925 N1.getValueType() == VT && "Binary operator types must match!");
2926 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2927 // it's worth handling here.
2928 if (N2C && N2C->isNullValue())
2938 assert(VT.isInteger() && "This operator does not apply to FP types!");
2939 assert(N1.getValueType() == N2.getValueType() &&
2940 N1.getValueType() == VT && "Binary operator types must match!");
2947 if (getTarget().Options.UnsafeFPMath) {
2948 if (Opcode == ISD::FADD) {
2950 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2951 if (CFP->getValueAPF().isZero())
2954 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2955 if (CFP->getValueAPF().isZero())
2957 } else if (Opcode == ISD::FSUB) {
2959 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2960 if (CFP->getValueAPF().isZero())
2962 } else if (Opcode == ISD::FMUL) {
2963 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2966 // If the first operand isn't the constant, try the second
2968 CFP = dyn_cast<ConstantFPSDNode>(N2);
2975 return SDValue(CFP,0);
2977 if (CFP->isExactlyValue(1.0))
2982 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2983 assert(N1.getValueType() == N2.getValueType() &&
2984 N1.getValueType() == VT && "Binary operator types must match!");
2986 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2987 assert(N1.getValueType() == VT &&
2988 N1.getValueType().isFloatingPoint() &&
2989 N2.getValueType().isFloatingPoint() &&
2990 "Invalid FCOPYSIGN!");
2997 assert(VT == N1.getValueType() &&
2998 "Shift operators return type must be the same as their first arg");
2999 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3000 "Shifts only work on integers");
3001 assert((!VT.isVector() || VT == N2.getValueType()) &&
3002 "Vector shift amounts must be in the same as their first arg");
3003 // Verify that the shift amount VT is bit enough to hold valid shift
3004 // amounts. This catches things like trying to shift an i1024 value by an
3005 // i8, which is easy to fall into in generic code that uses
3006 // TLI.getShiftAmount().
3007 assert(N2.getValueType().getSizeInBits() >=
3008 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3009 "Invalid use of small shift amount with oversized value!");
3011 // Always fold shifts of i1 values so the code generator doesn't need to
3012 // handle them. Since we know the size of the shift has to be less than the
3013 // size of the value, the shift/rotate count is guaranteed to be zero.
3016 if (N2C && N2C->isNullValue())
3019 case ISD::FP_ROUND_INREG: {
3020 EVT EVT = cast<VTSDNode>(N2)->getVT();
3021 assert(VT == N1.getValueType() && "Not an inreg round!");
3022 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3023 "Cannot FP_ROUND_INREG integer types");
3024 assert(EVT.isVector() == VT.isVector() &&
3025 "FP_ROUND_INREG type should be vector iff the operand "
3027 assert((!EVT.isVector() ||
3028 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3029 "Vector element counts must match in FP_ROUND_INREG");
3030 assert(EVT.bitsLE(VT) && "Not rounding down!");
3032 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3036 assert(VT.isFloatingPoint() &&
3037 N1.getValueType().isFloatingPoint() &&
3038 VT.bitsLE(N1.getValueType()) &&
3039 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3040 if (N1.getValueType() == VT) return N1; // noop conversion.
3042 case ISD::AssertSext:
3043 case ISD::AssertZext: {
3044 EVT EVT = cast<VTSDNode>(N2)->getVT();
3045 assert(VT == N1.getValueType() && "Not an inreg extend!");
3046 assert(VT.isInteger() && EVT.isInteger() &&
3047 "Cannot *_EXTEND_INREG FP types");
3048 assert(!EVT.isVector() &&
3049 "AssertSExt/AssertZExt type should be the vector element type "
3050 "rather than the vector type!");
3051 assert(EVT.bitsLE(VT) && "Not extending!");
3052 if (VT == EVT) return N1; // noop assertion.
3055 case ISD::SIGN_EXTEND_INREG: {
3056 EVT EVT = cast<VTSDNode>(N2)->getVT();
3057 assert(VT == N1.getValueType() && "Not an inreg extend!");
3058 assert(VT.isInteger() && EVT.isInteger() &&
3059 "Cannot *_EXTEND_INREG FP types");
3060 assert(EVT.isVector() == VT.isVector() &&
3061 "SIGN_EXTEND_INREG type should be vector iff the operand "
3063 assert((!EVT.isVector() ||
3064 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3065 "Vector element counts must match in SIGN_EXTEND_INREG");
3066 assert(EVT.bitsLE(VT) && "Not extending!");
3067 if (EVT == VT) return N1; // Not actually extending
3070 APInt Val = N1C->getAPIntValue();
3071 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3072 Val <<= Val.getBitWidth()-FromBits;
3073 Val = Val.ashr(Val.getBitWidth()-FromBits);
3074 return getConstant(Val, VT);
3078 case ISD::EXTRACT_VECTOR_ELT:
3079 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3080 if (N1.getOpcode() == ISD::UNDEF)
3081 return getUNDEF(VT);
3083 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3084 // expanding copies of large vectors from registers.
3086 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3087 N1.getNumOperands() > 0) {
3089 N1.getOperand(0).getValueType().getVectorNumElements();
3090 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3091 N1.getOperand(N2C->getZExtValue() / Factor),
3092 getConstant(N2C->getZExtValue() % Factor,
3093 N2.getValueType()));
3096 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3097 // expanding large vector constants.
3098 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3099 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3101 if (VT != Elt.getValueType())
3102 // If the vector element type is not legal, the BUILD_VECTOR operands
3103 // are promoted and implicitly truncated, and the result implicitly
3104 // extended. Make that explicit here.
3105 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3110 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3111 // operations are lowered to scalars.
3112 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3113 // If the indices are the same, return the inserted element else
3114 // if the indices are known different, extract the element from
3115 // the original vector.
3116 SDValue N1Op2 = N1.getOperand(2);
3117 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3119 if (N1Op2C && N2C) {
3120 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3121 if (VT == N1.getOperand(1).getValueType())
3122 return N1.getOperand(1);
3124 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3127 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3131 case ISD::EXTRACT_ELEMENT:
3132 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3133 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3134 (N1.getValueType().isInteger() == VT.isInteger()) &&
3135 N1.getValueType() != VT &&
3136 "Wrong types for EXTRACT_ELEMENT!");
3138 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3139 // 64-bit integers into 32-bit parts. Instead of building the extract of
3140 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3141 if (N1.getOpcode() == ISD::BUILD_PAIR)
3142 return N1.getOperand(N2C->getZExtValue());
3144 // EXTRACT_ELEMENT of a constant int is also very common.
3145 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3146 unsigned ElementSize = VT.getSizeInBits();
3147 unsigned Shift = ElementSize * N2C->getZExtValue();
3148 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3149 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3152 case ISD::EXTRACT_SUBVECTOR: {
3154 if (VT.isSimple() && N1.getValueType().isSimple()) {
3155 assert(VT.isVector() && N1.getValueType().isVector() &&
3156 "Extract subvector VTs must be a vectors!");
3157 assert(VT.getVectorElementType() ==
3158 N1.getValueType().getVectorElementType() &&
3159 "Extract subvector VTs must have the same element type!");
3160 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3161 "Extract subvector must be from larger vector to smaller vector!");
3163 if (isa<ConstantSDNode>(Index.getNode())) {
3164 assert((VT.getVectorNumElements() +
3165 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3166 <= N1.getValueType().getVectorNumElements())
3167 && "Extract subvector overflow!");
3170 // Trivial extraction.
3171 if (VT.getSimpleVT() == N1.getSimpleValueType())
3178 // Perform trivial constant folding.
3179 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3180 if (SV.getNode()) return SV;
3182 // Canonicalize constant to RHS if commutative.
3183 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3184 std::swap(N1C, N2C);
3188 // Constant fold FP operations.
3189 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3190 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3192 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3193 // Canonicalize constant to RHS if commutative.
3194 std::swap(N1CFP, N2CFP);
3197 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3198 APFloat::opStatus s;
3201 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3202 if (s != APFloat::opInvalidOp)
3203 return getConstantFP(V1, VT);
3206 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3207 if (s!=APFloat::opInvalidOp)
3208 return getConstantFP(V1, VT);
3211 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3212 if (s!=APFloat::opInvalidOp)
3213 return getConstantFP(V1, VT);
3216 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3217 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3218 return getConstantFP(V1, VT);
3221 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3222 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3223 return getConstantFP(V1, VT);
3225 case ISD::FCOPYSIGN:
3227 return getConstantFP(V1, VT);
3232 if (Opcode == ISD::FP_ROUND) {
3233 APFloat V = N1CFP->getValueAPF(); // make copy
3235 // This can return overflow, underflow, or inexact; we don't care.
3236 // FIXME need to be more flexible about rounding mode.
3237 (void)V.convert(EVTToAPFloatSemantics(VT),
3238 APFloat::rmNearestTiesToEven, &ignored);
3239 return getConstantFP(V, VT);
3243 // Canonicalize an UNDEF to the RHS, even over a constant.
3244 if (N1.getOpcode() == ISD::UNDEF) {
3245 if (isCommutativeBinOp(Opcode)) {
3249 case ISD::FP_ROUND_INREG:
3250 case ISD::SIGN_EXTEND_INREG:
3256 return N1; // fold op(undef, arg2) -> undef
3264 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3265 // For vectors, we can't easily build an all zero vector, just return
3272 // Fold a bunch of operators when the RHS is undef.
3273 if (N2.getOpcode() == ISD::UNDEF) {
3276 if (N1.getOpcode() == ISD::UNDEF)
3277 // Handle undef ^ undef -> 0 special case. This is a common
3279 return getConstant(0, VT);
3289 return N2; // fold op(arg1, undef) -> undef
3295 if (getTarget().Options.UnsafeFPMath)
3303 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3304 // For vectors, we can't easily build an all zero vector, just return
3309 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3310 // For vectors, we can't easily build an all one vector, just return
3318 // Memoize this node if possible.
3320 SDVTList VTs = getVTList(VT);
3321 if (VT != MVT::Glue) {
3322 SDValue Ops[] = { N1, N2 };
3323 FoldingSetNodeID ID;
3324 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3326 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3327 return SDValue(E, 0);
3329 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3330 DL.getDebugLoc(), VTs, N1, N2);
3331 CSEMap.InsertNode(N, IP);
3333 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3334 DL.getDebugLoc(), VTs, N1, N2);
3337 AllNodes.push_back(N);
3341 return SDValue(N, 0);
3344 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3345 SDValue N1, SDValue N2, SDValue N3) {
3346 // Perform various simplifications.
3347 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3350 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3351 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3352 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3353 if (N1CFP && N2CFP && N3CFP) {
3354 APFloat V1 = N1CFP->getValueAPF();
3355 const APFloat &V2 = N2CFP->getValueAPF();
3356 const APFloat &V3 = N3CFP->getValueAPF();
3357 APFloat::opStatus s =
3358 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3359 if (s != APFloat::opInvalidOp)
3360 return getConstantFP(V1, VT);
3364 case ISD::CONCAT_VECTORS:
3365 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3366 // one big BUILD_VECTOR.
3367 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3368 N2.getOpcode() == ISD::BUILD_VECTOR &&
3369 N3.getOpcode() == ISD::BUILD_VECTOR) {
3370 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3371 N1.getNode()->op_end());
3372 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3373 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3374 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3378 // Use FoldSetCC to simplify SETCC's.
3379 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3380 if (Simp.getNode()) return Simp;
3385 if (N1C->getZExtValue())
3386 return N2; // select true, X, Y -> X
3387 return N3; // select false, X, Y -> Y
3390 if (N2 == N3) return N2; // select C, X, X -> X
3392 case ISD::VECTOR_SHUFFLE:
3393 llvm_unreachable("should use getVectorShuffle constructor!");
3394 case ISD::INSERT_SUBVECTOR: {
3396 if (VT.isSimple() && N1.getValueType().isSimple()
3397 && N2.getValueType().isSimple()) {
3398 assert(VT.isVector() && N1.getValueType().isVector() &&
3399 N2.getValueType().isVector() &&
3400 "Insert subvector VTs must be a vectors");
3401 assert(VT == N1.getValueType() &&
3402 "Dest and insert subvector source types must match!");
3403 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3404 "Insert subvector must be from smaller vector to larger vector!");
3405 if (isa<ConstantSDNode>(Index.getNode())) {
3406 assert((N2.getValueType().getVectorNumElements() +
3407 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3408 <= VT.getVectorNumElements())
3409 && "Insert subvector overflow!");
3412 // Trivial insertion.
3413 if (VT.getSimpleVT() == N2.getSimpleValueType())
3419 // Fold bit_convert nodes from a type to themselves.
3420 if (N1.getValueType() == VT)
3425 // Memoize node if it doesn't produce a flag.
3427 SDVTList VTs = getVTList(VT);
3428 if (VT != MVT::Glue) {
3429 SDValue Ops[] = { N1, N2, N3 };
3430 FoldingSetNodeID ID;
3431 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3433 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3434 return SDValue(E, 0);
3436 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3437 DL.getDebugLoc(), VTs, N1, N2, N3);
3438 CSEMap.InsertNode(N, IP);
3440 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3441 DL.getDebugLoc(), VTs, N1, N2, N3);
3444 AllNodes.push_back(N);
3448 return SDValue(N, 0);
3451 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3452 SDValue N1, SDValue N2, SDValue N3,
3454 SDValue Ops[] = { N1, N2, N3, N4 };
3455 return getNode(Opcode, DL, VT, Ops, 4);
3458 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3459 SDValue N1, SDValue N2, SDValue N3,
3460 SDValue N4, SDValue N5) {
3461 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3462 return getNode(Opcode, DL, VT, Ops, 5);
3465 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3466 /// the incoming stack arguments to be loaded from the stack.
3467 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3468 SmallVector<SDValue, 8> ArgChains;
3470 // Include the original chain at the beginning of the list. When this is
3471 // used by target LowerCall hooks, this helps legalize find the
3472 // CALLSEQ_BEGIN node.
3473 ArgChains.push_back(Chain);
3475 // Add a chain value for each stack argument.
3476 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3477 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3478 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3479 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3480 if (FI->getIndex() < 0)
3481 ArgChains.push_back(SDValue(L, 1));
3483 // Build a tokenfactor for all the chains.
3484 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other,
3485 &ArgChains[0], ArgChains.size());
3488 /// getMemsetValue - Vectorized representation of the memset value
3490 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3492 assert(Value.getOpcode() != ISD::UNDEF);
3494 unsigned NumBits = VT.getScalarType().getSizeInBits();
3495 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3496 assert(C->getAPIntValue().getBitWidth() == 8);
3497 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3499 return DAG.getConstant(Val, VT);
3500 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3503 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3505 // Use a multiplication with 0x010101... to extend the input to the
3507 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3508 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3514 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3515 /// used when a memcpy is turned into a memset when the source is a constant
3517 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3518 const TargetLowering &TLI, StringRef Str) {
3519 // Handle vector with all elements zero.
3522 return DAG.getConstant(0, VT);
3523 else if (VT == MVT::f32 || VT == MVT::f64)
3524 return DAG.getConstantFP(0.0, VT);
3525 else if (VT.isVector()) {
3526 unsigned NumElts = VT.getVectorNumElements();
3527 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3528 return DAG.getNode(ISD::BITCAST, dl, VT,
3529 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3532 llvm_unreachable("Expected type!");
3535 assert(!VT.isVector() && "Can't handle vector type here!");
3536 unsigned NumVTBits = VT.getSizeInBits();
3537 unsigned NumVTBytes = NumVTBits / 8;
3538 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3540 APInt Val(NumVTBits, 0);
3541 if (TLI.isLittleEndian()) {
3542 for (unsigned i = 0; i != NumBytes; ++i)
3543 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3545 for (unsigned i = 0; i != NumBytes; ++i)
3546 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3549 // If the "cost" of materializing the integer immediate is 1 or free, then
3550 // it is cost effective to turn the load into the immediate.
3551 const TargetTransformInfo *TTI = DAG.getTargetTransformInfo();
3552 if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) < 2)
3553 return DAG.getConstant(Val, VT);
3554 return SDValue(0, 0);
3557 /// getMemBasePlusOffset - Returns base and offset node for the
3559 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3560 SelectionDAG &DAG) {
3561 EVT VT = Base.getValueType();
3562 return DAG.getNode(ISD::ADD, dl,
3563 VT, Base, DAG.getConstant(Offset, VT));
3566 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3568 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3569 unsigned SrcDelta = 0;
3570 GlobalAddressSDNode *G = NULL;
3571 if (Src.getOpcode() == ISD::GlobalAddress)
3572 G = cast<GlobalAddressSDNode>(Src);
3573 else if (Src.getOpcode() == ISD::ADD &&
3574 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3575 Src.getOperand(1).getOpcode() == ISD::Constant) {
3576 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3577 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3582 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3585 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3586 /// to replace the memset / memcpy. Return true if the number of memory ops
3587 /// is below the threshold. It returns the types of the sequence of
3588 /// memory ops to perform memset / memcpy by reference.
3589 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3590 unsigned Limit, uint64_t Size,
3591 unsigned DstAlign, unsigned SrcAlign,
3597 const TargetLowering &TLI) {
3598 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3599 "Expecting memcpy / memset source to meet alignment requirement!");
3600 // If 'SrcAlign' is zero, that means the memory operation does not need to
3601 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3602 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3603 // is the specified alignment of the memory operation. If it is zero, that
3604 // means it's possible to change the alignment of the destination.
3605 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3606 // not need to be loaded.
3607 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3608 IsMemset, ZeroMemset, MemcpyStrSrc,
3609 DAG.getMachineFunction());
3611 if (VT == MVT::Other) {
3612 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment() ||
3613 TLI.allowsUnalignedMemoryAccesses(VT)) {
3614 VT = TLI.getPointerTy();
3616 switch (DstAlign & 7) {
3617 case 0: VT = MVT::i64; break;
3618 case 4: VT = MVT::i32; break;
3619 case 2: VT = MVT::i16; break;
3620 default: VT = MVT::i8; break;
3625 while (!TLI.isTypeLegal(LVT))
3626 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3627 assert(LVT.isInteger());
3633 unsigned NumMemOps = 0;
3635 unsigned VTSize = VT.getSizeInBits() / 8;
3636 while (VTSize > Size) {
3637 // For now, only use non-vector load / store's for the left-over pieces.
3642 if (VT.isVector() || VT.isFloatingPoint()) {
3643 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3644 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3645 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3647 else if (NewVT == MVT::i64 &&
3648 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3649 TLI.isSafeMemOpType(MVT::f64)) {
3650 // i64 is usually not legal on 32-bit targets, but f64 may be.
3658 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3659 if (NewVT == MVT::i8)
3661 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3663 NewVTSize = NewVT.getSizeInBits() / 8;
3665 // If the new VT cannot cover all of the remaining bits, then consider
3666 // issuing a (or a pair of) unaligned and overlapping load / store.
3667 // FIXME: Only does this for 64-bit or more since we don't have proper
3668 // cost model for unaligned load / store.
3670 if (NumMemOps && AllowOverlap &&
3671 VTSize >= 8 && NewVTSize < Size &&
3672 TLI.allowsUnalignedMemoryAccesses(VT, &Fast) && Fast)
3680 if (++NumMemOps > Limit)
3683 MemOps.push_back(VT);
3690 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3691 SDValue Chain, SDValue Dst,
3692 SDValue Src, uint64_t Size,
3693 unsigned Align, bool isVol,
3695 MachinePointerInfo DstPtrInfo,
3696 MachinePointerInfo SrcPtrInfo) {
3697 // Turn a memcpy of undef to nop.
3698 if (Src.getOpcode() == ISD::UNDEF)
3701 // Expand memcpy to a series of load and store ops if the size operand falls
3702 // below a certain threshold.
3703 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3704 // rather than maybe a humongous number of loads and stores.
3705 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3706 std::vector<EVT> MemOps;
3707 bool DstAlignCanChange = false;
3708 MachineFunction &MF = DAG.getMachineFunction();
3709 MachineFrameInfo *MFI = MF.getFrameInfo();
3711 MF.getFunction()->getAttributes().
3712 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3713 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3714 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3715 DstAlignCanChange = true;
3716 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3717 if (Align > SrcAlign)
3720 bool CopyFromStr = isMemSrcFromString(Src, Str);
3721 bool isZeroStr = CopyFromStr && Str.empty();
3722 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3724 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3725 (DstAlignCanChange ? 0 : Align),
3726 (isZeroStr ? 0 : SrcAlign),
3727 false, false, CopyFromStr, true, DAG, TLI))
3730 if (DstAlignCanChange) {
3731 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3732 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3734 // Don't promote to an alignment that would require dynamic stack
3736 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3737 if (!TRI->needsStackRealignment(MF))
3738 while (NewAlign > Align &&
3739 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3742 if (NewAlign > Align) {
3743 // Give the stack frame object a larger alignment if needed.
3744 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3745 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3750 SmallVector<SDValue, 8> OutChains;
3751 unsigned NumMemOps = MemOps.size();
3752 uint64_t SrcOff = 0, DstOff = 0;
3753 for (unsigned i = 0; i != NumMemOps; ++i) {
3755 unsigned VTSize = VT.getSizeInBits() / 8;
3756 SDValue Value, Store;
3758 if (VTSize > Size) {
3759 // Issuing an unaligned load / store pair that overlaps with the previous
3760 // pair. Adjust the offset accordingly.
3761 assert(i == NumMemOps-1 && i != 0);
3762 SrcOff -= VTSize - Size;
3763 DstOff -= VTSize - Size;
3767 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3768 // It's unlikely a store of a vector immediate can be done in a single
3769 // instruction. It would require a load from a constantpool first.
3770 // We only handle zero vectors here.
3771 // FIXME: Handle other cases where store of vector immediate is done in
3772 // a single instruction.
3773 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3774 if (Value.getNode())
3775 Store = DAG.getStore(Chain, dl, Value,
3776 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3777 DstPtrInfo.getWithOffset(DstOff), isVol,
3781 if (!Store.getNode()) {
3782 // The type might not be legal for the target. This should only happen
3783 // if the type is smaller than a legal type, as on PPC, so the right
3784 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3785 // to Load/Store if NVT==VT.
3786 // FIXME does the case above also need this?
3787 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3788 assert(NVT.bitsGE(VT));
3789 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3790 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3791 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3792 MinAlign(SrcAlign, SrcOff));
3793 Store = DAG.getTruncStore(Chain, dl, Value,
3794 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3795 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3798 OutChains.push_back(Store);
3804 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3805 &OutChains[0], OutChains.size());
3808 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3809 SDValue Chain, SDValue Dst,
3810 SDValue Src, uint64_t Size,
3811 unsigned Align, bool isVol,
3813 MachinePointerInfo DstPtrInfo,
3814 MachinePointerInfo SrcPtrInfo) {
3815 // Turn a memmove of undef to nop.
3816 if (Src.getOpcode() == ISD::UNDEF)
3819 // Expand memmove to a series of load and store ops if the size operand falls
3820 // below a certain threshold.
3821 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3822 std::vector<EVT> MemOps;
3823 bool DstAlignCanChange = false;
3824 MachineFunction &MF = DAG.getMachineFunction();
3825 MachineFrameInfo *MFI = MF.getFrameInfo();
3826 bool OptSize = MF.getFunction()->getAttributes().
3827 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3828 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3829 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3830 DstAlignCanChange = true;
3831 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3832 if (Align > SrcAlign)
3834 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3836 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3837 (DstAlignCanChange ? 0 : Align), SrcAlign,
3838 false, false, false, false, DAG, TLI))
3841 if (DstAlignCanChange) {
3842 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3843 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3844 if (NewAlign > Align) {
3845 // Give the stack frame object a larger alignment if needed.
3846 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3847 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3852 uint64_t SrcOff = 0, DstOff = 0;
3853 SmallVector<SDValue, 8> LoadValues;
3854 SmallVector<SDValue, 8> LoadChains;
3855 SmallVector<SDValue, 8> OutChains;
3856 unsigned NumMemOps = MemOps.size();
3857 for (unsigned i = 0; i < NumMemOps; i++) {
3859 unsigned VTSize = VT.getSizeInBits() / 8;
3862 Value = DAG.getLoad(VT, dl, Chain,
3863 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3864 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3865 false, false, SrcAlign);
3866 LoadValues.push_back(Value);
3867 LoadChains.push_back(Value.getValue(1));
3870 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3871 &LoadChains[0], LoadChains.size());
3873 for (unsigned i = 0; i < NumMemOps; i++) {
3875 unsigned VTSize = VT.getSizeInBits() / 8;
3878 Store = DAG.getStore(Chain, dl, LoadValues[i],
3879 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3880 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3881 OutChains.push_back(Store);
3885 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3886 &OutChains[0], OutChains.size());
3889 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3892 /// \param DAG Selection DAG where lowered code is placed.
3893 /// \param dl Link to corresponding IR location.
3894 /// \param Chain Control flow dependency.
3895 /// \param Dst Pointer to destination memory location.
3896 /// \param Src Value of byte to write into the memory.
3897 /// \param Size Number of bytes to write.
3898 /// \param Align Alignment of the destination in bytes.
3899 /// \param isVol True if destination is volatile.
3900 /// \param DstPtrInfo IR information on the memory pointer.
3901 /// \returns New head in the control flow, if lowering was successful, empty
3902 /// SDValue otherwise.
3904 /// The function tries to replace 'llvm.memset' intrinsic with several store
3905 /// operations and value calculation code. This is usually profitable for small
3907 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3908 SDValue Chain, SDValue Dst,
3909 SDValue Src, uint64_t Size,
3910 unsigned Align, bool isVol,
3911 MachinePointerInfo DstPtrInfo) {
3912 // Turn a memset of undef to nop.
3913 if (Src.getOpcode() == ISD::UNDEF)
3916 // Expand memset to a series of load/store ops if the size operand
3917 // falls below a certain threshold.
3918 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3919 std::vector<EVT> MemOps;
3920 bool DstAlignCanChange = false;
3921 MachineFunction &MF = DAG.getMachineFunction();
3922 MachineFrameInfo *MFI = MF.getFrameInfo();
3923 bool OptSize = MF.getFunction()->getAttributes().
3924 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3925 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3926 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3927 DstAlignCanChange = true;
3929 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3930 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3931 Size, (DstAlignCanChange ? 0 : Align), 0,
3932 true, IsZeroVal, false, true, DAG, TLI))
3935 if (DstAlignCanChange) {
3936 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3937 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3938 if (NewAlign > Align) {
3939 // Give the stack frame object a larger alignment if needed.
3940 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3941 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3946 SmallVector<SDValue, 8> OutChains;
3947 uint64_t DstOff = 0;
3948 unsigned NumMemOps = MemOps.size();
3950 // Find the largest store and generate the bit pattern for it.
3951 EVT LargestVT = MemOps[0];
3952 for (unsigned i = 1; i < NumMemOps; i++)
3953 if (MemOps[i].bitsGT(LargestVT))
3954 LargestVT = MemOps[i];
3955 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3957 for (unsigned i = 0; i < NumMemOps; i++) {
3959 unsigned VTSize = VT.getSizeInBits() / 8;
3960 if (VTSize > Size) {
3961 // Issuing an unaligned load / store pair that overlaps with the previous
3962 // pair. Adjust the offset accordingly.
3963 assert(i == NumMemOps-1 && i != 0);
3964 DstOff -= VTSize - Size;
3967 // If this store is smaller than the largest store see whether we can get
3968 // the smaller value for free with a truncate.
3969 SDValue Value = MemSetValue;
3970 if (VT.bitsLT(LargestVT)) {
3971 if (!LargestVT.isVector() && !VT.isVector() &&
3972 TLI.isTruncateFree(LargestVT, VT))
3973 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3975 Value = getMemsetValue(Src, VT, DAG, dl);
3977 assert(Value.getValueType() == VT && "Value with wrong type.");
3978 SDValue Store = DAG.getStore(Chain, dl, Value,
3979 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3980 DstPtrInfo.getWithOffset(DstOff),
3981 isVol, false, Align);
3982 OutChains.push_back(Store);
3983 DstOff += VT.getSizeInBits() / 8;
3987 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3988 &OutChains[0], OutChains.size());
3991 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
3992 SDValue Src, SDValue Size,
3993 unsigned Align, bool isVol, bool AlwaysInline,
3994 MachinePointerInfo DstPtrInfo,
3995 MachinePointerInfo SrcPtrInfo) {
3996 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
3998 // Check to see if we should lower the memcpy to loads and stores first.
3999 // For cases within the target-specified limits, this is the best choice.
4000 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4002 // Memcpy with size zero? Just return the original chain.
4003 if (ConstantSize->isNullValue())
4006 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4007 ConstantSize->getZExtValue(),Align,
4008 isVol, false, DstPtrInfo, SrcPtrInfo);
4009 if (Result.getNode())
4013 // Then check to see if we should lower the memcpy with target-specific
4014 // code. If the target chooses to do this, this is the next best.
4016 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4017 isVol, AlwaysInline,
4018 DstPtrInfo, SrcPtrInfo);
4019 if (Result.getNode())
4022 // If we really need inline code and the target declined to provide it,
4023 // use a (potentially long) sequence of loads and stores.
4025 assert(ConstantSize && "AlwaysInline requires a constant size!");
4026 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4027 ConstantSize->getZExtValue(), Align, isVol,
4028 true, DstPtrInfo, SrcPtrInfo);
4031 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4032 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4033 // respect volatile, so they may do things like read or write memory
4034 // beyond the given memory regions. But fixing this isn't easy, and most
4035 // people don't care.
4037 const TargetLowering *TLI = TM.getTargetLowering();
4039 // Emit a library call.
4040 TargetLowering::ArgListTy Args;
4041 TargetLowering::ArgListEntry Entry;
4042 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4043 Entry.Node = Dst; Args.push_back(Entry);
4044 Entry.Node = Src; Args.push_back(Entry);
4045 Entry.Node = Size; Args.push_back(Entry);
4046 // FIXME: pass in SDLoc
4048 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4049 false, false, false, false, 0,
4050 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4051 /*isTailCall=*/false,
4052 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4053 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4054 TLI->getPointerTy()),
4056 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4058 return CallResult.second;
4061 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4062 SDValue Src, SDValue Size,
4063 unsigned Align, bool isVol,
4064 MachinePointerInfo DstPtrInfo,
4065 MachinePointerInfo SrcPtrInfo) {
4066 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4068 // Check to see if we should lower the memmove to loads and stores first.
4069 // For cases within the target-specified limits, this is the best choice.
4070 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4072 // Memmove with size zero? Just return the original chain.
4073 if (ConstantSize->isNullValue())
4077 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4078 ConstantSize->getZExtValue(), Align, isVol,
4079 false, DstPtrInfo, SrcPtrInfo);
4080 if (Result.getNode())
4084 // Then check to see if we should lower the memmove with target-specific
4085 // code. If the target chooses to do this, this is the next best.
4087 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4088 DstPtrInfo, SrcPtrInfo);
4089 if (Result.getNode())
4092 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4093 // not be safe. See memcpy above for more details.
4095 const TargetLowering *TLI = TM.getTargetLowering();
4097 // Emit a library call.
4098 TargetLowering::ArgListTy Args;
4099 TargetLowering::ArgListEntry Entry;
4100 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4101 Entry.Node = Dst; Args.push_back(Entry);
4102 Entry.Node = Src; Args.push_back(Entry);
4103 Entry.Node = Size; Args.push_back(Entry);
4104 // FIXME: pass in SDLoc
4106 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4107 false, false, false, false, 0,
4108 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4109 /*isTailCall=*/false,
4110 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4111 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4112 TLI->getPointerTy()),
4114 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4116 return CallResult.second;
4119 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4120 SDValue Src, SDValue Size,
4121 unsigned Align, bool isVol,
4122 MachinePointerInfo DstPtrInfo) {
4123 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4125 // Check to see if we should lower the memset to stores first.
4126 // For cases within the target-specified limits, this is the best choice.
4127 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4129 // Memset with size zero? Just return the original chain.
4130 if (ConstantSize->isNullValue())
4134 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4135 Align, isVol, DstPtrInfo);
4137 if (Result.getNode())
4141 // Then check to see if we should lower the memset with target-specific
4142 // code. If the target chooses to do this, this is the next best.
4144 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4146 if (Result.getNode())
4149 // Emit a library call.
4150 const TargetLowering *TLI = TM.getTargetLowering();
4151 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4152 TargetLowering::ArgListTy Args;
4153 TargetLowering::ArgListEntry Entry;
4154 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4155 Args.push_back(Entry);
4156 // Extend or truncate the argument to be an i32 value for the call.
4157 if (Src.getValueType().bitsGT(MVT::i32))
4158 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4160 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4162 Entry.Ty = Type::getInt32Ty(*getContext());
4163 Entry.isSExt = true;
4164 Args.push_back(Entry);
4166 Entry.Ty = IntPtrTy;
4167 Entry.isSExt = false;
4168 Args.push_back(Entry);
4169 // FIXME: pass in SDLoc
4171 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4172 false, false, false, false, 0,
4173 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4174 /*isTailCall=*/false,
4175 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4176 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4177 TLI->getPointerTy()),
4179 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4181 return CallResult.second;
4184 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4185 SDVTList VTList, SDValue* Ops, unsigned NumOps,
4186 MachineMemOperand *MMO,
4187 AtomicOrdering Ordering,
4188 SynchronizationScope SynchScope) {
4189 FoldingSetNodeID ID;
4190 ID.AddInteger(MemVT.getRawBits());
4191 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4192 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4194 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4195 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4196 return SDValue(E, 0);
4199 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4200 // SDNode doesn't have access to it. This memory will be "leaked" when
4201 // the node is deallocated, but recovered when the allocator is released.
4202 // If the number of operands is less than 5 we use AtomicSDNode's internal
4204 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4206 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4207 dl.getDebugLoc(), VTList, MemVT,
4208 Ops, DynOps, NumOps, MMO,
4209 Ordering, SynchScope);
4210 CSEMap.InsertNode(N, IP);
4211 AllNodes.push_back(N);
4212 return SDValue(N, 0);
4215 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4216 SDValue Chain, SDValue Ptr, SDValue Cmp,
4217 SDValue Swp, MachinePointerInfo PtrInfo,
4219 AtomicOrdering Ordering,
4220 SynchronizationScope SynchScope) {
4221 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4222 Alignment = getEVTAlignment(MemVT);
4224 MachineFunction &MF = getMachineFunction();
4226 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4227 // For now, atomics are considered to be volatile always.
4228 // FIXME: Volatile isn't really correct; we should keep track of atomic
4229 // orderings in the memoperand.
4230 unsigned Flags = MachineMemOperand::MOVolatile;
4231 if (Opcode != ISD::ATOMIC_STORE)
4232 Flags |= MachineMemOperand::MOLoad;
4233 if (Opcode != ISD::ATOMIC_LOAD)
4234 Flags |= MachineMemOperand::MOStore;
4236 MachineMemOperand *MMO =
4237 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4239 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4240 Ordering, SynchScope);
4243 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4245 SDValue Ptr, SDValue Cmp,
4246 SDValue Swp, MachineMemOperand *MMO,
4247 AtomicOrdering Ordering,
4248 SynchronizationScope SynchScope) {
4249 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4250 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4252 EVT VT = Cmp.getValueType();
4254 SDVTList VTs = getVTList(VT, MVT::Other);
4255 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4256 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, Ordering, SynchScope);
4259 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4261 SDValue Ptr, SDValue Val,
4262 const Value* PtrVal,
4264 AtomicOrdering Ordering,
4265 SynchronizationScope SynchScope) {
4266 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4267 Alignment = getEVTAlignment(MemVT);
4269 MachineFunction &MF = getMachineFunction();
4270 // An atomic store does not load. An atomic load does not store.
4271 // (An atomicrmw obviously both loads and stores.)
4272 // For now, atomics are considered to be volatile always, and they are
4274 // FIXME: Volatile isn't really correct; we should keep track of atomic
4275 // orderings in the memoperand.
4276 unsigned Flags = MachineMemOperand::MOVolatile;
4277 if (Opcode != ISD::ATOMIC_STORE)
4278 Flags |= MachineMemOperand::MOLoad;
4279 if (Opcode != ISD::ATOMIC_LOAD)
4280 Flags |= MachineMemOperand::MOStore;
4282 MachineMemOperand *MMO =
4283 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4284 MemVT.getStoreSize(), Alignment);
4286 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4287 Ordering, SynchScope);
4290 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4292 SDValue Ptr, SDValue Val,
4293 MachineMemOperand *MMO,
4294 AtomicOrdering Ordering,
4295 SynchronizationScope SynchScope) {
4296 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4297 Opcode == ISD::ATOMIC_LOAD_SUB ||
4298 Opcode == ISD::ATOMIC_LOAD_AND ||
4299 Opcode == ISD::ATOMIC_LOAD_OR ||
4300 Opcode == ISD::ATOMIC_LOAD_XOR ||
4301 Opcode == ISD::ATOMIC_LOAD_NAND ||
4302 Opcode == ISD::ATOMIC_LOAD_MIN ||
4303 Opcode == ISD::ATOMIC_LOAD_MAX ||
4304 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4305 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4306 Opcode == ISD::ATOMIC_SWAP ||
4307 Opcode == ISD::ATOMIC_STORE) &&
4308 "Invalid Atomic Op");
4310 EVT VT = Val.getValueType();
4312 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4313 getVTList(VT, MVT::Other);
4314 SDValue Ops[] = {Chain, Ptr, Val};
4315 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4318 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4319 EVT VT, SDValue Chain,
4321 const Value* PtrVal,
4323 AtomicOrdering Ordering,
4324 SynchronizationScope SynchScope) {
4325 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4326 Alignment = getEVTAlignment(MemVT);
4328 MachineFunction &MF = getMachineFunction();
4329 // An atomic store does not load. An atomic load does not store.
4330 // (An atomicrmw obviously both loads and stores.)
4331 // For now, atomics are considered to be volatile always, and they are
4333 // FIXME: Volatile isn't really correct; we should keep track of atomic
4334 // orderings in the memoperand.
4335 unsigned Flags = MachineMemOperand::MOVolatile;
4336 if (Opcode != ISD::ATOMIC_STORE)
4337 Flags |= MachineMemOperand::MOLoad;
4338 if (Opcode != ISD::ATOMIC_LOAD)
4339 Flags |= MachineMemOperand::MOStore;
4341 MachineMemOperand *MMO =
4342 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4343 MemVT.getStoreSize(), Alignment);
4345 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4346 Ordering, SynchScope);
4349 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4350 EVT VT, SDValue Chain,
4352 MachineMemOperand *MMO,
4353 AtomicOrdering Ordering,
4354 SynchronizationScope SynchScope) {
4355 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4357 SDVTList VTs = getVTList(VT, MVT::Other);
4358 SDValue Ops[] = {Chain, Ptr};
4359 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4362 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4363 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4368 SmallVector<EVT, 4> VTs;
4369 VTs.reserve(NumOps);
4370 for (unsigned i = 0; i < NumOps; ++i)
4371 VTs.push_back(Ops[i].getValueType());
4372 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4377 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4378 const EVT *VTs, unsigned NumVTs,
4379 const SDValue *Ops, unsigned NumOps,
4380 EVT MemVT, MachinePointerInfo PtrInfo,
4381 unsigned Align, bool Vol,
4382 bool ReadMem, bool WriteMem) {
4383 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4384 MemVT, PtrInfo, Align, Vol,
4389 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4390 const SDValue *Ops, unsigned NumOps,
4391 EVT MemVT, MachinePointerInfo PtrInfo,
4392 unsigned Align, bool Vol,
4393 bool ReadMem, bool WriteMem) {
4394 if (Align == 0) // Ensure that codegen never sees alignment 0
4395 Align = getEVTAlignment(MemVT);
4397 MachineFunction &MF = getMachineFunction();
4400 Flags |= MachineMemOperand::MOStore;
4402 Flags |= MachineMemOperand::MOLoad;
4404 Flags |= MachineMemOperand::MOVolatile;
4405 MachineMemOperand *MMO =
4406 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4408 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4412 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4413 const SDValue *Ops, unsigned NumOps,
4414 EVT MemVT, MachineMemOperand *MMO) {
4415 assert((Opcode == ISD::INTRINSIC_VOID ||
4416 Opcode == ISD::INTRINSIC_W_CHAIN ||
4417 Opcode == ISD::PREFETCH ||
4418 Opcode == ISD::LIFETIME_START ||
4419 Opcode == ISD::LIFETIME_END ||
4420 (Opcode <= INT_MAX &&
4421 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4422 "Opcode is not a memory-accessing opcode!");
4424 // Memoize the node unless it returns a flag.
4425 MemIntrinsicSDNode *N;
4426 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4427 FoldingSetNodeID ID;
4428 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4429 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4431 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4432 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4433 return SDValue(E, 0);
4436 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4437 dl.getDebugLoc(), VTList, Ops,
4438 NumOps, MemVT, MMO);
4439 CSEMap.InsertNode(N, IP);
4441 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4442 dl.getDebugLoc(), VTList, Ops,
4443 NumOps, MemVT, MMO);
4445 AllNodes.push_back(N);
4446 return SDValue(N, 0);
4449 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4450 /// MachinePointerInfo record from it. This is particularly useful because the
4451 /// code generator has many cases where it doesn't bother passing in a
4452 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4453 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4454 // If this is FI+Offset, we can model it.
4455 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4456 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4458 // If this is (FI+Offset1)+Offset2, we can model it.
4459 if (Ptr.getOpcode() != ISD::ADD ||
4460 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4461 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4462 return MachinePointerInfo();
4464 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4465 return MachinePointerInfo::getFixedStack(FI, Offset+
4466 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4469 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4470 /// MachinePointerInfo record from it. This is particularly useful because the
4471 /// code generator has many cases where it doesn't bother passing in a
4472 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4473 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4474 // If the 'Offset' value isn't a constant, we can't handle this.
4475 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4476 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4477 if (OffsetOp.getOpcode() == ISD::UNDEF)
4478 return InferPointerInfo(Ptr);
4479 return MachinePointerInfo();
4484 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4485 EVT VT, SDLoc dl, SDValue Chain,
4486 SDValue Ptr, SDValue Offset,
4487 MachinePointerInfo PtrInfo, EVT MemVT,
4488 bool isVolatile, bool isNonTemporal, bool isInvariant,
4489 unsigned Alignment, const MDNode *TBAAInfo,
4490 const MDNode *Ranges) {
4491 assert(Chain.getValueType() == MVT::Other &&
4492 "Invalid chain type");
4493 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4494 Alignment = getEVTAlignment(VT);
4496 unsigned Flags = MachineMemOperand::MOLoad;
4498 Flags |= MachineMemOperand::MOVolatile;
4500 Flags |= MachineMemOperand::MONonTemporal;
4502 Flags |= MachineMemOperand::MOInvariant;
4504 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4507 PtrInfo = InferPointerInfo(Ptr, Offset);
4509 MachineFunction &MF = getMachineFunction();
4510 MachineMemOperand *MMO =
4511 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4513 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4517 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4518 EVT VT, SDLoc dl, SDValue Chain,
4519 SDValue Ptr, SDValue Offset, EVT MemVT,
4520 MachineMemOperand *MMO) {
4522 ExtType = ISD::NON_EXTLOAD;
4523 } else if (ExtType == ISD::NON_EXTLOAD) {
4524 assert(VT == MemVT && "Non-extending load from different memory type!");
4527 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4528 "Should only be an extending load, not truncating!");
4529 assert(VT.isInteger() == MemVT.isInteger() &&
4530 "Cannot convert from FP to Int or Int -> FP!");
4531 assert(VT.isVector() == MemVT.isVector() &&
4532 "Cannot use trunc store to convert to or from a vector!");
4533 assert((!VT.isVector() ||
4534 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4535 "Cannot use trunc store to change the number of vector elements!");
4538 bool Indexed = AM != ISD::UNINDEXED;
4539 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4540 "Unindexed load with an offset!");
4542 SDVTList VTs = Indexed ?
4543 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4544 SDValue Ops[] = { Chain, Ptr, Offset };
4545 FoldingSetNodeID ID;
4546 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4547 ID.AddInteger(MemVT.getRawBits());
4548 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4549 MMO->isNonTemporal(),
4550 MMO->isInvariant()));
4551 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4553 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4554 cast<LoadSDNode>(E)->refineAlignment(MMO);
4555 return SDValue(E, 0);
4557 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4558 dl.getDebugLoc(), VTs, AM, ExtType,
4560 CSEMap.InsertNode(N, IP);
4561 AllNodes.push_back(N);
4562 return SDValue(N, 0);
4565 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4566 SDValue Chain, SDValue Ptr,
4567 MachinePointerInfo PtrInfo,
4568 bool isVolatile, bool isNonTemporal,
4569 bool isInvariant, unsigned Alignment,
4570 const MDNode *TBAAInfo,
4571 const MDNode *Ranges) {
4572 SDValue Undef = getUNDEF(Ptr.getValueType());
4573 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4574 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4578 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4579 SDValue Chain, SDValue Ptr,
4580 MachineMemOperand *MMO) {
4581 SDValue Undef = getUNDEF(Ptr.getValueType());
4582 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4586 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4587 SDValue Chain, SDValue Ptr,
4588 MachinePointerInfo PtrInfo, EVT MemVT,
4589 bool isVolatile, bool isNonTemporal,
4590 unsigned Alignment, const MDNode *TBAAInfo) {
4591 SDValue Undef = getUNDEF(Ptr.getValueType());
4592 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4593 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4598 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4599 SDValue Chain, SDValue Ptr, EVT MemVT,
4600 MachineMemOperand *MMO) {
4601 SDValue Undef = getUNDEF(Ptr.getValueType());
4602 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4607 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4608 SDValue Offset, ISD::MemIndexedMode AM) {
4609 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4610 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4611 "Load is already a indexed load!");
4612 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4613 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4614 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4615 false, LD->getAlignment());
4618 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4619 SDValue Ptr, MachinePointerInfo PtrInfo,
4620 bool isVolatile, bool isNonTemporal,
4621 unsigned Alignment, const MDNode *TBAAInfo) {
4622 assert(Chain.getValueType() == MVT::Other &&
4623 "Invalid chain type");
4624 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4625 Alignment = getEVTAlignment(Val.getValueType());
4627 unsigned Flags = MachineMemOperand::MOStore;
4629 Flags |= MachineMemOperand::MOVolatile;
4631 Flags |= MachineMemOperand::MONonTemporal;
4634 PtrInfo = InferPointerInfo(Ptr);
4636 MachineFunction &MF = getMachineFunction();
4637 MachineMemOperand *MMO =
4638 MF.getMachineMemOperand(PtrInfo, Flags,
4639 Val.getValueType().getStoreSize(), Alignment,
4642 return getStore(Chain, dl, Val, Ptr, MMO);
4645 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4646 SDValue Ptr, MachineMemOperand *MMO) {
4647 assert(Chain.getValueType() == MVT::Other &&
4648 "Invalid chain type");
4649 EVT VT = Val.getValueType();
4650 SDVTList VTs = getVTList(MVT::Other);
4651 SDValue Undef = getUNDEF(Ptr.getValueType());
4652 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4653 FoldingSetNodeID ID;
4654 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4655 ID.AddInteger(VT.getRawBits());
4656 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4657 MMO->isNonTemporal(), MMO->isInvariant()));
4658 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4661 cast<StoreSDNode>(E)->refineAlignment(MMO);
4662 return SDValue(E, 0);
4664 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4665 dl.getDebugLoc(), VTs,
4666 ISD::UNINDEXED, false, VT, MMO);
4667 CSEMap.InsertNode(N, IP);
4668 AllNodes.push_back(N);
4669 return SDValue(N, 0);
4672 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4673 SDValue Ptr, MachinePointerInfo PtrInfo,
4674 EVT SVT,bool isVolatile, bool isNonTemporal,
4676 const MDNode *TBAAInfo) {
4677 assert(Chain.getValueType() == MVT::Other &&
4678 "Invalid chain type");
4679 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4680 Alignment = getEVTAlignment(SVT);
4682 unsigned Flags = MachineMemOperand::MOStore;
4684 Flags |= MachineMemOperand::MOVolatile;
4686 Flags |= MachineMemOperand::MONonTemporal;
4689 PtrInfo = InferPointerInfo(Ptr);
4691 MachineFunction &MF = getMachineFunction();
4692 MachineMemOperand *MMO =
4693 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4696 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4699 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4700 SDValue Ptr, EVT SVT,
4701 MachineMemOperand *MMO) {
4702 EVT VT = Val.getValueType();
4704 assert(Chain.getValueType() == MVT::Other &&
4705 "Invalid chain type");
4707 return getStore(Chain, dl, Val, Ptr, MMO);
4709 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4710 "Should only be a truncating store, not extending!");
4711 assert(VT.isInteger() == SVT.isInteger() &&
4712 "Can't do FP-INT conversion!");
4713 assert(VT.isVector() == SVT.isVector() &&
4714 "Cannot use trunc store to convert to or from a vector!");
4715 assert((!VT.isVector() ||
4716 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4717 "Cannot use trunc store to change the number of vector elements!");
4719 SDVTList VTs = getVTList(MVT::Other);
4720 SDValue Undef = getUNDEF(Ptr.getValueType());
4721 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4722 FoldingSetNodeID ID;
4723 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4724 ID.AddInteger(SVT.getRawBits());
4725 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4726 MMO->isNonTemporal(), MMO->isInvariant()));
4727 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4729 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4730 cast<StoreSDNode>(E)->refineAlignment(MMO);
4731 return SDValue(E, 0);
4733 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4734 dl.getDebugLoc(), VTs,
4735 ISD::UNINDEXED, true, SVT, MMO);
4736 CSEMap.InsertNode(N, IP);
4737 AllNodes.push_back(N);
4738 return SDValue(N, 0);
4742 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4743 SDValue Offset, ISD::MemIndexedMode AM) {
4744 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4745 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4746 "Store is already a indexed store!");
4747 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4748 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4749 FoldingSetNodeID ID;
4750 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4751 ID.AddInteger(ST->getMemoryVT().getRawBits());
4752 ID.AddInteger(ST->getRawSubclassData());
4753 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4755 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4756 return SDValue(E, 0);
4758 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4759 dl.getDebugLoc(), VTs, AM,
4760 ST->isTruncatingStore(),
4762 ST->getMemOperand());
4763 CSEMap.InsertNode(N, IP);
4764 AllNodes.push_back(N);
4765 return SDValue(N, 0);
4768 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4769 SDValue Chain, SDValue Ptr,
4772 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4773 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4776 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4777 const SDUse *Ops, unsigned NumOps) {
4779 case 0: return getNode(Opcode, DL, VT);
4780 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4781 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4782 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4786 // Copy from an SDUse array into an SDValue array for use with
4787 // the regular getNode logic.
4788 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4789 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4792 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4793 const SDValue *Ops, unsigned NumOps) {
4795 case 0: return getNode(Opcode, DL, VT);
4796 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4797 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4798 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4804 case ISD::SELECT_CC: {
4805 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4806 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4807 "LHS and RHS of condition must have same type!");
4808 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4809 "True and False arms of SelectCC must have same type!");
4810 assert(Ops[2].getValueType() == VT &&
4811 "select_cc node must be of same type as true and false value!");
4815 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4816 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4817 "LHS/RHS of comparison should match types!");
4824 SDVTList VTs = getVTList(VT);
4826 if (VT != MVT::Glue) {
4827 FoldingSetNodeID ID;
4828 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4831 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4832 return SDValue(E, 0);
4834 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4836 CSEMap.InsertNode(N, IP);
4838 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4842 AllNodes.push_back(N);
4846 return SDValue(N, 0);
4849 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4850 ArrayRef<EVT> ResultTys,
4851 const SDValue *Ops, unsigned NumOps) {
4852 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4856 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4857 const EVT *VTs, unsigned NumVTs,
4858 const SDValue *Ops, unsigned NumOps) {
4860 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4861 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4864 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4865 const SDValue *Ops, unsigned NumOps) {
4866 if (VTList.NumVTs == 1)
4867 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4871 // FIXME: figure out how to safely handle things like
4872 // int foo(int x) { return 1 << (x & 255); }
4873 // int bar() { return foo(256); }
4874 case ISD::SRA_PARTS:
4875 case ISD::SRL_PARTS:
4876 case ISD::SHL_PARTS:
4877 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4878 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4879 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4880 else if (N3.getOpcode() == ISD::AND)
4881 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4882 // If the and is only masking out bits that cannot effect the shift,
4883 // eliminate the and.
4884 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4885 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4886 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4892 // Memoize the node unless it returns a flag.
4894 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4895 FoldingSetNodeID ID;
4896 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4898 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4899 return SDValue(E, 0);
4902 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4903 DL.getDebugLoc(), VTList, Ops[0]);
4904 } else if (NumOps == 2) {
4905 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4906 DL.getDebugLoc(), VTList, Ops[0],
4908 } else if (NumOps == 3) {
4909 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4910 DL.getDebugLoc(), VTList, Ops[0],
4913 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4914 VTList, Ops, NumOps);
4916 CSEMap.InsertNode(N, IP);
4919 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4920 DL.getDebugLoc(), VTList, Ops[0]);
4921 } else if (NumOps == 2) {
4922 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4923 DL.getDebugLoc(), VTList, Ops[0],
4925 } else if (NumOps == 3) {
4926 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4927 DL.getDebugLoc(), VTList, Ops[0],
4930 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4931 VTList, Ops, NumOps);
4934 AllNodes.push_back(N);
4938 return SDValue(N, 0);
4941 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4942 return getNode(Opcode, DL, VTList, 0, 0);
4945 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4947 SDValue Ops[] = { N1 };
4948 return getNode(Opcode, DL, VTList, Ops, 1);
4951 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4952 SDValue N1, SDValue N2) {
4953 SDValue Ops[] = { N1, N2 };
4954 return getNode(Opcode, DL, VTList, Ops, 2);
4957 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4958 SDValue N1, SDValue N2, SDValue N3) {
4959 SDValue Ops[] = { N1, N2, N3 };
4960 return getNode(Opcode, DL, VTList, Ops, 3);
4963 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4964 SDValue N1, SDValue N2, SDValue N3,
4966 SDValue Ops[] = { N1, N2, N3, N4 };
4967 return getNode(Opcode, DL, VTList, Ops, 4);
4970 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4971 SDValue N1, SDValue N2, SDValue N3,
4972 SDValue N4, SDValue N5) {
4973 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4974 return getNode(Opcode, DL, VTList, Ops, 5);
4977 SDVTList SelectionDAG::getVTList(EVT VT) {
4978 return makeVTList(SDNode::getValueTypeList(VT), 1);
4981 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4982 FoldingSetNodeID ID;
4984 ID.AddInteger(VT1.getRawBits());
4985 ID.AddInteger(VT2.getRawBits());
4988 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
4989 if (Result == NULL) {
4990 EVT *Array = Allocator.Allocate<EVT>(2);
4993 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
4994 VTListMap.InsertNode(Result, IP);
4996 return Result->getSDVTList();
4999 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5000 FoldingSetNodeID ID;
5002 ID.AddInteger(VT1.getRawBits());
5003 ID.AddInteger(VT2.getRawBits());
5004 ID.AddInteger(VT3.getRawBits());
5007 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5008 if (Result == NULL) {
5009 EVT *Array = Allocator.Allocate<EVT>(3);
5013 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5014 VTListMap.InsertNode(Result, IP);
5016 return Result->getSDVTList();
5019 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5020 FoldingSetNodeID ID;
5022 ID.AddInteger(VT1.getRawBits());
5023 ID.AddInteger(VT2.getRawBits());
5024 ID.AddInteger(VT3.getRawBits());
5025 ID.AddInteger(VT4.getRawBits());
5028 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5029 if (Result == NULL) {
5030 EVT *Array = Allocator.Allocate<EVT>(4);
5035 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5036 VTListMap.InsertNode(Result, IP);
5038 return Result->getSDVTList();
5041 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5042 FoldingSetNodeID ID;
5043 ID.AddInteger(NumVTs);
5044 for (unsigned index = 0; index < NumVTs; index++) {
5045 ID.AddInteger(VTs[index].getRawBits());
5049 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5050 if (Result == NULL) {
5051 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5052 std::copy(VTs, VTs + NumVTs, Array);
5053 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5054 VTListMap.InsertNode(Result, IP);
5056 return Result->getSDVTList();
5060 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5061 /// specified operands. If the resultant node already exists in the DAG,
5062 /// this does not modify the specified node, instead it returns the node that
5063 /// already exists. If the resultant node does not exist in the DAG, the
5064 /// input node is returned. As a degenerate case, if you specify the same
5065 /// input operands as the node already has, the input node is returned.
5066 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5067 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5069 // Check to see if there is no change.
5070 if (Op == N->getOperand(0)) return N;
5072 // See if the modified node already exists.
5073 void *InsertPos = 0;
5074 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5077 // Nope it doesn't. Remove the node from its current place in the maps.
5079 if (!RemoveNodeFromCSEMaps(N))
5082 // Now we update the operands.
5083 N->OperandList[0].set(Op);
5085 // If this gets put into a CSE map, add it.
5086 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5090 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5091 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5093 // Check to see if there is no change.
5094 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5095 return N; // No operands changed, just return the input node.
5097 // See if the modified node already exists.
5098 void *InsertPos = 0;
5099 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5102 // Nope it doesn't. Remove the node from its current place in the maps.
5104 if (!RemoveNodeFromCSEMaps(N))
5107 // Now we update the operands.
5108 if (N->OperandList[0] != Op1)
5109 N->OperandList[0].set(Op1);
5110 if (N->OperandList[1] != Op2)
5111 N->OperandList[1].set(Op2);
5113 // If this gets put into a CSE map, add it.
5114 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5118 SDNode *SelectionDAG::
5119 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5120 SDValue Ops[] = { Op1, Op2, Op3 };
5121 return UpdateNodeOperands(N, Ops, 3);
5124 SDNode *SelectionDAG::
5125 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5126 SDValue Op3, SDValue Op4) {
5127 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5128 return UpdateNodeOperands(N, Ops, 4);
5131 SDNode *SelectionDAG::
5132 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5133 SDValue Op3, SDValue Op4, SDValue Op5) {
5134 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5135 return UpdateNodeOperands(N, Ops, 5);
5138 SDNode *SelectionDAG::
5139 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5140 assert(N->getNumOperands() == NumOps &&
5141 "Update with wrong number of operands");
5143 // Check to see if there is no change.
5144 bool AnyChange = false;
5145 for (unsigned i = 0; i != NumOps; ++i) {
5146 if (Ops[i] != N->getOperand(i)) {
5152 // No operands changed, just return the input node.
5153 if (!AnyChange) return N;
5155 // See if the modified node already exists.
5156 void *InsertPos = 0;
5157 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5160 // Nope it doesn't. Remove the node from its current place in the maps.
5162 if (!RemoveNodeFromCSEMaps(N))
5165 // Now we update the operands.
5166 for (unsigned i = 0; i != NumOps; ++i)
5167 if (N->OperandList[i] != Ops[i])
5168 N->OperandList[i].set(Ops[i]);
5170 // If this gets put into a CSE map, add it.
5171 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5175 /// DropOperands - Release the operands and set this node to have
5177 void SDNode::DropOperands() {
5178 // Unlike the code in MorphNodeTo that does this, we don't need to
5179 // watch for dead nodes here.
5180 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5186 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5189 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5191 SDVTList VTs = getVTList(VT);
5192 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5195 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5196 EVT VT, SDValue Op1) {
5197 SDVTList VTs = getVTList(VT);
5198 SDValue Ops[] = { Op1 };
5199 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5202 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5203 EVT VT, SDValue Op1,
5205 SDVTList VTs = getVTList(VT);
5206 SDValue Ops[] = { Op1, Op2 };
5207 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5210 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5211 EVT VT, SDValue Op1,
5212 SDValue Op2, SDValue Op3) {
5213 SDVTList VTs = getVTList(VT);
5214 SDValue Ops[] = { Op1, Op2, Op3 };
5215 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5218 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5219 EVT VT, const SDValue *Ops,
5221 SDVTList VTs = getVTList(VT);
5222 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5225 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5226 EVT VT1, EVT VT2, const SDValue *Ops,
5228 SDVTList VTs = getVTList(VT1, VT2);
5229 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5232 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5234 SDVTList VTs = getVTList(VT1, VT2);
5235 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5238 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5239 EVT VT1, EVT VT2, EVT VT3,
5240 const SDValue *Ops, unsigned NumOps) {
5241 SDVTList VTs = getVTList(VT1, VT2, VT3);
5242 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5245 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5246 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5247 const SDValue *Ops, unsigned NumOps) {
5248 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5249 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5252 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5255 SDVTList VTs = getVTList(VT1, VT2);
5256 SDValue Ops[] = { Op1 };
5257 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5260 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5262 SDValue Op1, SDValue Op2) {
5263 SDVTList VTs = getVTList(VT1, VT2);
5264 SDValue Ops[] = { Op1, Op2 };
5265 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5268 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 SDValue Op1, SDValue Op2,
5272 SDVTList VTs = getVTList(VT1, VT2);
5273 SDValue Ops[] = { Op1, Op2, Op3 };
5274 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5277 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5278 EVT VT1, EVT VT2, EVT VT3,
5279 SDValue Op1, SDValue Op2,
5281 SDVTList VTs = getVTList(VT1, VT2, VT3);
5282 SDValue Ops[] = { Op1, Op2, Op3 };
5283 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5286 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5287 SDVTList VTs, const SDValue *Ops,
5289 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5290 // Reset the NodeID to -1.
5295 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5296 /// the line number information on the merged node since it is not possible to
5297 /// preserve the information that operation is associated with multiple lines.
5298 /// This will make the debugger working better at -O0, were there is a higher
5299 /// probability having other instructions associated with that line.
5301 /// For IROrder, we keep the smaller of the two
5302 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5303 DebugLoc NLoc = N->getDebugLoc();
5304 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5305 (OLoc.getDebugLoc() != NLoc)) {
5306 N->setDebugLoc(DebugLoc());
5308 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5309 N->setIROrder(Order);
5313 /// MorphNodeTo - This *mutates* the specified node to have the specified
5314 /// return type, opcode, and operands.
5316 /// Note that MorphNodeTo returns the resultant node. If there is already a
5317 /// node of the specified opcode and operands, it returns that node instead of
5318 /// the current one. Note that the SDLoc need not be the same.
5320 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5321 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5322 /// node, and because it doesn't require CSE recalculation for any of
5323 /// the node's users.
5325 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5326 SDVTList VTs, const SDValue *Ops,
5328 // If an identical node already exists, use it.
5330 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5331 FoldingSetNodeID ID;
5332 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5333 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5334 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5337 if (!RemoveNodeFromCSEMaps(N))
5340 // Start the morphing.
5342 N->ValueList = VTs.VTs;
5343 N->NumValues = VTs.NumVTs;
5345 // Clear the operands list, updating used nodes to remove this from their
5346 // use list. Keep track of any operands that become dead as a result.
5347 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5348 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5350 SDNode *Used = Use.getNode();
5352 if (Used->use_empty())
5353 DeadNodeSet.insert(Used);
5356 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5357 // Initialize the memory references information.
5358 MN->setMemRefs(0, 0);
5359 // If NumOps is larger than the # of operands we can have in a
5360 // MachineSDNode, reallocate the operand list.
5361 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5362 if (MN->OperandsNeedDelete)
5363 delete[] MN->OperandList;
5364 if (NumOps > array_lengthof(MN->LocalOperands))
5365 // We're creating a final node that will live unmorphed for the
5366 // remainder of the current SelectionDAG iteration, so we can allocate
5367 // the operands directly out of a pool with no recycling metadata.
5368 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5371 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5372 MN->OperandsNeedDelete = false;
5374 MN->InitOperands(MN->OperandList, Ops, NumOps);
5376 // If NumOps is larger than the # of operands we currently have, reallocate
5377 // the operand list.
5378 if (NumOps > N->NumOperands) {
5379 if (N->OperandsNeedDelete)
5380 delete[] N->OperandList;
5381 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5382 N->OperandsNeedDelete = true;
5384 N->InitOperands(N->OperandList, Ops, NumOps);
5387 // Delete any nodes that are still dead after adding the uses for the
5389 if (!DeadNodeSet.empty()) {
5390 SmallVector<SDNode *, 16> DeadNodes;
5391 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5392 E = DeadNodeSet.end(); I != E; ++I)
5393 if ((*I)->use_empty())
5394 DeadNodes.push_back(*I);
5395 RemoveDeadNodes(DeadNodes);
5399 CSEMap.InsertNode(N, IP); // Memoize the new node.
5404 /// getMachineNode - These are used for target selectors to create a new node
5405 /// with specified return type(s), MachineInstr opcode, and operands.
5407 /// Note that getMachineNode returns the resultant node. If there is already a
5408 /// node of the specified opcode and operands, it returns that node instead of
5409 /// the current one.
5411 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5412 SDVTList VTs = getVTList(VT);
5413 return getMachineNode(Opcode, dl, VTs, None);
5417 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5418 SDVTList VTs = getVTList(VT);
5419 SDValue Ops[] = { Op1 };
5420 return getMachineNode(Opcode, dl, VTs, Ops);
5424 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5425 SDValue Op1, SDValue Op2) {
5426 SDVTList VTs = getVTList(VT);
5427 SDValue Ops[] = { Op1, Op2 };
5428 return getMachineNode(Opcode, dl, VTs, Ops);
5432 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5433 SDValue Op1, SDValue Op2, SDValue Op3) {
5434 SDVTList VTs = getVTList(VT);
5435 SDValue Ops[] = { Op1, Op2, Op3 };
5436 return getMachineNode(Opcode, dl, VTs, Ops);
5440 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5441 ArrayRef<SDValue> Ops) {
5442 SDVTList VTs = getVTList(VT);
5443 return getMachineNode(Opcode, dl, VTs, Ops);
5447 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5448 SDVTList VTs = getVTList(VT1, VT2);
5449 return getMachineNode(Opcode, dl, VTs, None);
5453 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5454 EVT VT1, EVT VT2, SDValue Op1) {
5455 SDVTList VTs = getVTList(VT1, VT2);
5456 SDValue Ops[] = { Op1 };
5457 return getMachineNode(Opcode, dl, VTs, Ops);
5461 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5462 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5463 SDVTList VTs = getVTList(VT1, VT2);
5464 SDValue Ops[] = { Op1, Op2 };
5465 return getMachineNode(Opcode, dl, VTs, Ops);
5469 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5470 EVT VT1, EVT VT2, SDValue Op1,
5471 SDValue Op2, SDValue Op3) {
5472 SDVTList VTs = getVTList(VT1, VT2);
5473 SDValue Ops[] = { Op1, Op2, Op3 };
5474 return getMachineNode(Opcode, dl, VTs, Ops);
5478 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5480 ArrayRef<SDValue> Ops) {
5481 SDVTList VTs = getVTList(VT1, VT2);
5482 return getMachineNode(Opcode, dl, VTs, Ops);
5486 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5487 EVT VT1, EVT VT2, EVT VT3,
5488 SDValue Op1, SDValue Op2) {
5489 SDVTList VTs = getVTList(VT1, VT2, VT3);
5490 SDValue Ops[] = { Op1, Op2 };
5491 return getMachineNode(Opcode, dl, VTs, Ops);
5495 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5496 EVT VT1, EVT VT2, EVT VT3,
5497 SDValue Op1, SDValue Op2, SDValue Op3) {
5498 SDVTList VTs = getVTList(VT1, VT2, VT3);
5499 SDValue Ops[] = { Op1, Op2, Op3 };
5500 return getMachineNode(Opcode, dl, VTs, Ops);
5504 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5505 EVT VT1, EVT VT2, EVT VT3,
5506 ArrayRef<SDValue> Ops) {
5507 SDVTList VTs = getVTList(VT1, VT2, VT3);
5508 return getMachineNode(Opcode, dl, VTs, Ops);
5512 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5513 EVT VT2, EVT VT3, EVT VT4,
5514 ArrayRef<SDValue> Ops) {
5515 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5516 return getMachineNode(Opcode, dl, VTs, Ops);
5520 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5521 ArrayRef<EVT> ResultTys,
5522 ArrayRef<SDValue> Ops) {
5523 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5524 return getMachineNode(Opcode, dl, VTs, Ops);
5528 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5529 ArrayRef<SDValue> OpsArray) {
5530 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5533 const SDValue *Ops = OpsArray.data();
5534 unsigned NumOps = OpsArray.size();
5537 FoldingSetNodeID ID;
5538 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5540 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5541 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5545 // Allocate a new MachineSDNode.
5546 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5547 DL.getDebugLoc(), VTs);
5549 // Initialize the operands list.
5550 if (NumOps > array_lengthof(N->LocalOperands))
5551 // We're creating a final node that will live unmorphed for the
5552 // remainder of the current SelectionDAG iteration, so we can allocate
5553 // the operands directly out of a pool with no recycling metadata.
5554 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5557 N->InitOperands(N->LocalOperands, Ops, NumOps);
5558 N->OperandsNeedDelete = false;
5561 CSEMap.InsertNode(N, IP);
5563 AllNodes.push_back(N);
5565 VerifyMachineNode(N);
5570 /// getTargetExtractSubreg - A convenience function for creating
5571 /// TargetOpcode::EXTRACT_SUBREG nodes.
5573 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5575 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5576 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5577 VT, Operand, SRIdxVal);
5578 return SDValue(Subreg, 0);
5581 /// getTargetInsertSubreg - A convenience function for creating
5582 /// TargetOpcode::INSERT_SUBREG nodes.
5584 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5585 SDValue Operand, SDValue Subreg) {
5586 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5587 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5588 VT, Operand, Subreg, SRIdxVal);
5589 return SDValue(Result, 0);
5592 /// getNodeIfExists - Get the specified node if it's already available, or
5593 /// else return NULL.
5594 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5595 const SDValue *Ops, unsigned NumOps) {
5596 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5597 FoldingSetNodeID ID;
5598 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5600 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5606 /// getDbgValue - Creates a SDDbgValue node.
5609 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5610 DebugLoc DL, unsigned O) {
5611 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5615 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5616 DebugLoc DL, unsigned O) {
5617 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5621 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5622 DebugLoc DL, unsigned O) {
5623 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5628 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5629 /// pointed to by a use iterator is deleted, increment the use iterator
5630 /// so that it doesn't dangle.
5632 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5633 SDNode::use_iterator &UI;
5634 SDNode::use_iterator &UE;
5636 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5637 // Increment the iterator as needed.
5638 while (UI != UE && N == *UI)
5643 RAUWUpdateListener(SelectionDAG &d,
5644 SDNode::use_iterator &ui,
5645 SDNode::use_iterator &ue)
5646 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5651 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5652 /// This can cause recursive merging of nodes in the DAG.
5654 /// This version assumes From has a single result value.
5656 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5657 SDNode *From = FromN.getNode();
5658 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5659 "Cannot replace with this method!");
5660 assert(From != To.getNode() && "Cannot replace uses of with self");
5662 // Iterate over all the existing uses of From. New uses will be added
5663 // to the beginning of the use list, which we avoid visiting.
5664 // This specifically avoids visiting uses of From that arise while the
5665 // replacement is happening, because any such uses would be the result
5666 // of CSE: If an existing node looks like From after one of its operands
5667 // is replaced by To, we don't want to replace of all its users with To
5668 // too. See PR3018 for more info.
5669 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5670 RAUWUpdateListener Listener(*this, UI, UE);
5674 // This node is about to morph, remove its old self from the CSE maps.
5675 RemoveNodeFromCSEMaps(User);
5677 // A user can appear in a use list multiple times, and when this
5678 // happens the uses are usually next to each other in the list.
5679 // To help reduce the number of CSE recomputations, process all
5680 // the uses of this user that we can find this way.
5682 SDUse &Use = UI.getUse();
5685 } while (UI != UE && *UI == User);
5687 // Now that we have modified User, add it back to the CSE maps. If it
5688 // already exists there, recursively merge the results together.
5689 AddModifiedNodeToCSEMaps(User);
5692 // If we just RAUW'd the root, take note.
5693 if (FromN == getRoot())
5697 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5698 /// This can cause recursive merging of nodes in the DAG.
5700 /// This version assumes that for each value of From, there is a
5701 /// corresponding value in To in the same position with the same type.
5703 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5705 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5706 assert((!From->hasAnyUseOfValue(i) ||
5707 From->getValueType(i) == To->getValueType(i)) &&
5708 "Cannot use this version of ReplaceAllUsesWith!");
5711 // Handle the trivial case.
5715 // Iterate over just the existing users of From. See the comments in
5716 // the ReplaceAllUsesWith above.
5717 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5718 RAUWUpdateListener Listener(*this, UI, UE);
5722 // This node is about to morph, remove its old self from the CSE maps.
5723 RemoveNodeFromCSEMaps(User);
5725 // A user can appear in a use list multiple times, and when this
5726 // happens the uses are usually next to each other in the list.
5727 // To help reduce the number of CSE recomputations, process all
5728 // the uses of this user that we can find this way.
5730 SDUse &Use = UI.getUse();
5733 } while (UI != UE && *UI == User);
5735 // Now that we have modified User, add it back to the CSE maps. If it
5736 // already exists there, recursively merge the results together.
5737 AddModifiedNodeToCSEMaps(User);
5740 // If we just RAUW'd the root, take note.
5741 if (From == getRoot().getNode())
5742 setRoot(SDValue(To, getRoot().getResNo()));
5745 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5746 /// This can cause recursive merging of nodes in the DAG.
5748 /// This version can replace From with any result values. To must match the
5749 /// number and types of values returned by From.
5750 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5751 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5752 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5754 // Iterate over just the existing users of From. See the comments in
5755 // the ReplaceAllUsesWith above.
5756 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5757 RAUWUpdateListener Listener(*this, UI, UE);
5761 // This node is about to morph, remove its old self from the CSE maps.
5762 RemoveNodeFromCSEMaps(User);
5764 // A user can appear in a use list multiple times, and when this
5765 // happens the uses are usually next to each other in the list.
5766 // To help reduce the number of CSE recomputations, process all
5767 // the uses of this user that we can find this way.
5769 SDUse &Use = UI.getUse();
5770 const SDValue &ToOp = To[Use.getResNo()];
5773 } while (UI != UE && *UI == User);
5775 // Now that we have modified User, add it back to the CSE maps. If it
5776 // already exists there, recursively merge the results together.
5777 AddModifiedNodeToCSEMaps(User);
5780 // If we just RAUW'd the root, take note.
5781 if (From == getRoot().getNode())
5782 setRoot(SDValue(To[getRoot().getResNo()]));
5785 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5786 /// uses of other values produced by From.getNode() alone. The Deleted
5787 /// vector is handled the same way as for ReplaceAllUsesWith.
5788 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5789 // Handle the really simple, really trivial case efficiently.
5790 if (From == To) return;
5792 // Handle the simple, trivial, case efficiently.
5793 if (From.getNode()->getNumValues() == 1) {
5794 ReplaceAllUsesWith(From, To);
5798 // Iterate over just the existing users of From. See the comments in
5799 // the ReplaceAllUsesWith above.
5800 SDNode::use_iterator UI = From.getNode()->use_begin(),
5801 UE = From.getNode()->use_end();
5802 RAUWUpdateListener Listener(*this, UI, UE);
5805 bool UserRemovedFromCSEMaps = false;
5807 // A user can appear in a use list multiple times, and when this
5808 // happens the uses are usually next to each other in the list.
5809 // To help reduce the number of CSE recomputations, process all
5810 // the uses of this user that we can find this way.
5812 SDUse &Use = UI.getUse();
5814 // Skip uses of different values from the same node.
5815 if (Use.getResNo() != From.getResNo()) {
5820 // If this node hasn't been modified yet, it's still in the CSE maps,
5821 // so remove its old self from the CSE maps.
5822 if (!UserRemovedFromCSEMaps) {
5823 RemoveNodeFromCSEMaps(User);
5824 UserRemovedFromCSEMaps = true;
5829 } while (UI != UE && *UI == User);
5831 // We are iterating over all uses of the From node, so if a use
5832 // doesn't use the specific value, no changes are made.
5833 if (!UserRemovedFromCSEMaps)
5836 // Now that we have modified User, add it back to the CSE maps. If it
5837 // already exists there, recursively merge the results together.
5838 AddModifiedNodeToCSEMaps(User);
5841 // If we just RAUW'd the root, take note.
5842 if (From == getRoot())
5847 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5848 /// to record information about a use.
5855 /// operator< - Sort Memos by User.
5856 bool operator<(const UseMemo &L, const UseMemo &R) {
5857 return (intptr_t)L.User < (intptr_t)R.User;
5861 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5862 /// uses of other values produced by From.getNode() alone. The same value
5863 /// may appear in both the From and To list. The Deleted vector is
5864 /// handled the same way as for ReplaceAllUsesWith.
5865 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5868 // Handle the simple, trivial case efficiently.
5870 return ReplaceAllUsesOfValueWith(*From, *To);
5872 // Read up all the uses and make records of them. This helps
5873 // processing new uses that are introduced during the
5874 // replacement process.
5875 SmallVector<UseMemo, 4> Uses;
5876 for (unsigned i = 0; i != Num; ++i) {
5877 unsigned FromResNo = From[i].getResNo();
5878 SDNode *FromNode = From[i].getNode();
5879 for (SDNode::use_iterator UI = FromNode->use_begin(),
5880 E = FromNode->use_end(); UI != E; ++UI) {
5881 SDUse &Use = UI.getUse();
5882 if (Use.getResNo() == FromResNo) {
5883 UseMemo Memo = { *UI, i, &Use };
5884 Uses.push_back(Memo);
5889 // Sort the uses, so that all the uses from a given User are together.
5890 std::sort(Uses.begin(), Uses.end());
5892 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5893 UseIndex != UseIndexEnd; ) {
5894 // We know that this user uses some value of From. If it is the right
5895 // value, update it.
5896 SDNode *User = Uses[UseIndex].User;
5898 // This node is about to morph, remove its old self from the CSE maps.
5899 RemoveNodeFromCSEMaps(User);
5901 // The Uses array is sorted, so all the uses for a given User
5902 // are next to each other in the list.
5903 // To help reduce the number of CSE recomputations, process all
5904 // the uses of this user that we can find this way.
5906 unsigned i = Uses[UseIndex].Index;
5907 SDUse &Use = *Uses[UseIndex].Use;
5911 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5913 // Now that we have modified User, add it back to the CSE maps. If it
5914 // already exists there, recursively merge the results together.
5915 AddModifiedNodeToCSEMaps(User);
5919 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5920 /// based on their topological order. It returns the maximum id and a vector
5921 /// of the SDNodes* in assigned order by reference.
5922 unsigned SelectionDAG::AssignTopologicalOrder() {
5924 unsigned DAGSize = 0;
5926 // SortedPos tracks the progress of the algorithm. Nodes before it are
5927 // sorted, nodes after it are unsorted. When the algorithm completes
5928 // it is at the end of the list.
5929 allnodes_iterator SortedPos = allnodes_begin();
5931 // Visit all the nodes. Move nodes with no operands to the front of
5932 // the list immediately. Annotate nodes that do have operands with their
5933 // operand count. Before we do this, the Node Id fields of the nodes
5934 // may contain arbitrary values. After, the Node Id fields for nodes
5935 // before SortedPos will contain the topological sort index, and the
5936 // Node Id fields for nodes At SortedPos and after will contain the
5937 // count of outstanding operands.
5938 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5941 unsigned Degree = N->getNumOperands();
5943 // A node with no uses, add it to the result array immediately.
5944 N->setNodeId(DAGSize++);
5945 allnodes_iterator Q = N;
5947 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5948 assert(SortedPos != AllNodes.end() && "Overran node list");
5951 // Temporarily use the Node Id as scratch space for the degree count.
5952 N->setNodeId(Degree);
5956 // Visit all the nodes. As we iterate, move nodes into sorted order,
5957 // such that by the time the end is reached all nodes will be sorted.
5958 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5961 // N is in sorted position, so all its uses have one less operand
5962 // that needs to be sorted.
5963 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5966 unsigned Degree = P->getNodeId();
5967 assert(Degree != 0 && "Invalid node degree");
5970 // All of P's operands are sorted, so P may sorted now.
5971 P->setNodeId(DAGSize++);
5973 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5974 assert(SortedPos != AllNodes.end() && "Overran node list");
5977 // Update P's outstanding operand count.
5978 P->setNodeId(Degree);
5981 if (I == SortedPos) {
5984 dbgs() << "Overran sorted position:\n";
5987 llvm_unreachable(0);
5991 assert(SortedPos == AllNodes.end() &&
5992 "Topological sort incomplete!");
5993 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5994 "First node in topological sort is not the entry token!");
5995 assert(AllNodes.front().getNodeId() == 0 &&
5996 "First node in topological sort has non-zero id!");
5997 assert(AllNodes.front().getNumOperands() == 0 &&
5998 "First node in topological sort has operands!");
5999 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6000 "Last node in topologic sort has unexpected id!");
6001 assert(AllNodes.back().use_empty() &&
6002 "Last node in topologic sort has users!");
6003 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6007 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6008 /// value is produced by SD.
6009 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6010 DbgInfo->add(DB, SD, isParameter);
6012 SD->setHasDebugValue(true);
6015 /// TransferDbgValues - Transfer SDDbgValues.
6016 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6017 if (From == To || !From.getNode()->getHasDebugValue())
6019 SDNode *FromNode = From.getNode();
6020 SDNode *ToNode = To.getNode();
6021 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6022 SmallVector<SDDbgValue *, 2> ClonedDVs;
6023 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6025 SDDbgValue *Dbg = *I;
6026 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6027 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6028 Dbg->getOffset(), Dbg->getDebugLoc(),
6030 ClonedDVs.push_back(Clone);
6033 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6034 E = ClonedDVs.end(); I != E; ++I)
6035 AddDbgValue(*I, ToNode, false);
6038 //===----------------------------------------------------------------------===//
6040 //===----------------------------------------------------------------------===//
6042 HandleSDNode::~HandleSDNode() {
6046 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6047 DebugLoc DL, const GlobalValue *GA,
6048 EVT VT, int64_t o, unsigned char TF)
6049 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6053 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6054 SDValue X, unsigned SrcAS,
6056 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6057 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6059 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6060 EVT memvt, MachineMemOperand *mmo)
6061 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6062 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6063 MMO->isNonTemporal(), MMO->isInvariant());
6064 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6065 assert(isNonTemporal() == MMO->isNonTemporal() &&
6066 "Non-temporal encoding error!");
6067 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6070 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6071 const SDValue *Ops, unsigned NumOps, EVT memvt,
6072 MachineMemOperand *mmo)
6073 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6074 MemoryVT(memvt), MMO(mmo) {
6075 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6076 MMO->isNonTemporal(), MMO->isInvariant());
6077 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6078 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6081 /// Profile - Gather unique data for the node.
6083 void SDNode::Profile(FoldingSetNodeID &ID) const {
6084 AddNodeIDNode(ID, this);
6089 std::vector<EVT> VTs;
6092 VTs.reserve(MVT::LAST_VALUETYPE);
6093 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6094 VTs.push_back(MVT((MVT::SimpleValueType)i));
6099 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6100 static ManagedStatic<EVTArray> SimpleVTArray;
6101 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6103 /// getValueTypeList - Return a pointer to the specified value type.
6105 const EVT *SDNode::getValueTypeList(EVT VT) {
6106 if (VT.isExtended()) {
6107 sys::SmartScopedLock<true> Lock(*VTMutex);
6108 return &(*EVTs->insert(VT).first);
6110 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6111 "Value type out of range!");
6112 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6116 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6117 /// indicated value. This method ignores uses of other values defined by this
6119 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6120 assert(Value < getNumValues() && "Bad value!");
6122 // TODO: Only iterate over uses of a given value of the node
6123 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6124 if (UI.getUse().getResNo() == Value) {
6131 // Found exactly the right number of uses?
6136 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6137 /// value. This method ignores uses of other values defined by this operation.
6138 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6139 assert(Value < getNumValues() && "Bad value!");
6141 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6142 if (UI.getUse().getResNo() == Value)
6149 /// isOnlyUserOf - Return true if this node is the only use of N.
6151 bool SDNode::isOnlyUserOf(SDNode *N) const {
6153 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6164 /// isOperand - Return true if this node is an operand of N.
6166 bool SDValue::isOperandOf(SDNode *N) const {
6167 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6168 if (*this == N->getOperand(i))
6173 bool SDNode::isOperandOf(SDNode *N) const {
6174 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6175 if (this == N->OperandList[i].getNode())
6180 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6181 /// be a chain) reaches the specified operand without crossing any
6182 /// side-effecting instructions on any chain path. In practice, this looks
6183 /// through token factors and non-volatile loads. In order to remain efficient,
6184 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6185 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6186 unsigned Depth) const {
6187 if (*this == Dest) return true;
6189 // Don't search too deeply, we just want to be able to see through
6190 // TokenFactor's etc.
6191 if (Depth == 0) return false;
6193 // If this is a token factor, all inputs to the TF happen in parallel. If any
6194 // of the operands of the TF does not reach dest, then we cannot do the xform.
6195 if (getOpcode() == ISD::TokenFactor) {
6196 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6197 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6202 // Loads don't have side effects, look through them.
6203 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6204 if (!Ld->isVolatile())
6205 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6210 /// hasPredecessor - Return true if N is a predecessor of this node.
6211 /// N is either an operand of this node, or can be reached by recursively
6212 /// traversing up the operands.
6213 /// NOTE: This is an expensive method. Use it carefully.
6214 bool SDNode::hasPredecessor(const SDNode *N) const {
6215 SmallPtrSet<const SDNode *, 32> Visited;
6216 SmallVector<const SDNode *, 16> Worklist;
6217 return hasPredecessorHelper(N, Visited, Worklist);
6221 SDNode::hasPredecessorHelper(const SDNode *N,
6222 SmallPtrSet<const SDNode *, 32> &Visited,
6223 SmallVectorImpl<const SDNode *> &Worklist) const {
6224 if (Visited.empty()) {
6225 Worklist.push_back(this);
6227 // Take a look in the visited set. If we've already encountered this node
6228 // we needn't search further.
6229 if (Visited.count(N))
6233 // Haven't visited N yet. Continue the search.
6234 while (!Worklist.empty()) {
6235 const SDNode *M = Worklist.pop_back_val();
6236 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6237 SDNode *Op = M->getOperand(i).getNode();
6238 if (Visited.insert(Op))
6239 Worklist.push_back(Op);
6248 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6249 assert(Num < NumOperands && "Invalid child # of SDNode!");
6250 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6253 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6254 assert(N->getNumValues() == 1 &&
6255 "Can't unroll a vector with multiple results!");
6257 EVT VT = N->getValueType(0);
6258 unsigned NE = VT.getVectorNumElements();
6259 EVT EltVT = VT.getVectorElementType();
6262 SmallVector<SDValue, 8> Scalars;
6263 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6265 // If ResNE is 0, fully unroll the vector op.
6268 else if (NE > ResNE)
6272 for (i= 0; i != NE; ++i) {
6273 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6274 SDValue Operand = N->getOperand(j);
6275 EVT OperandVT = Operand.getValueType();
6276 if (OperandVT.isVector()) {
6277 // A vector operand; extract a single element.
6278 const TargetLowering *TLI = TM.getTargetLowering();
6279 EVT OperandEltVT = OperandVT.getVectorElementType();
6280 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6283 getConstant(i, TLI->getVectorIdxTy()));
6285 // A scalar operand; just use it as is.
6286 Operands[j] = Operand;
6290 switch (N->getOpcode()) {
6292 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6293 &Operands[0], Operands.size()));
6296 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6297 &Operands[0], Operands.size()));
6304 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6305 getShiftAmountOperand(Operands[0].getValueType(),
6308 case ISD::SIGN_EXTEND_INREG:
6309 case ISD::FP_ROUND_INREG: {
6310 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6311 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6313 getValueType(ExtVT)));
6318 for (; i < ResNE; ++i)
6319 Scalars.push_back(getUNDEF(EltVT));
6321 return getNode(ISD::BUILD_VECTOR, dl,
6322 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6323 &Scalars[0], Scalars.size());
6327 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6328 /// location that is 'Dist' units away from the location that the 'Base' load
6329 /// is loading from.
6330 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6331 unsigned Bytes, int Dist) const {
6332 if (LD->getChain() != Base->getChain())
6334 EVT VT = LD->getValueType(0);
6335 if (VT.getSizeInBits() / 8 != Bytes)
6338 SDValue Loc = LD->getOperand(1);
6339 SDValue BaseLoc = Base->getOperand(1);
6340 if (Loc.getOpcode() == ISD::FrameIndex) {
6341 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6343 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6344 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6345 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6346 int FS = MFI->getObjectSize(FI);
6347 int BFS = MFI->getObjectSize(BFI);
6348 if (FS != BFS || FS != (int)Bytes) return false;
6349 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6353 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6354 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6357 const GlobalValue *GV1 = NULL;
6358 const GlobalValue *GV2 = NULL;
6359 int64_t Offset1 = 0;
6360 int64_t Offset2 = 0;
6361 const TargetLowering *TLI = TM.getTargetLowering();
6362 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6363 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6364 if (isGA1 && isGA2 && GV1 == GV2)
6365 return Offset1 == (Offset2 + Dist*Bytes);
6370 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6371 /// it cannot be inferred.
6372 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6373 // If this is a GlobalAddress + cst, return the alignment.
6374 const GlobalValue *GV;
6375 int64_t GVOffset = 0;
6376 const TargetLowering *TLI = TM.getTargetLowering();
6377 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6378 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6379 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6380 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6381 TLI->getDataLayout());
6382 unsigned AlignBits = KnownZero.countTrailingOnes();
6383 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6385 return MinAlign(Align, GVOffset);
6388 // If this is a direct reference to a stack slot, use information about the
6389 // stack slot's alignment.
6390 int FrameIdx = 1 << 31;
6391 int64_t FrameOffset = 0;
6392 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6393 FrameIdx = FI->getIndex();
6394 } else if (isBaseWithConstantOffset(Ptr) &&
6395 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6397 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6398 FrameOffset = Ptr.getConstantOperandVal(1);
6401 if (FrameIdx != (1 << 31)) {
6402 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6403 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6411 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6412 /// which is split (or expanded) into two not necessarily identical pieces.
6413 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6414 // Currently all types are split in half.
6416 if (!VT.isVector()) {
6417 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6419 unsigned NumElements = VT.getVectorNumElements();
6420 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6421 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6424 return std::make_pair(LoVT, HiVT);
6427 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6429 std::pair<SDValue, SDValue>
6430 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6432 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6433 N.getValueType().getVectorNumElements() &&
6434 "More vector elements requested than available!");
6436 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6437 getConstant(0, TLI->getVectorIdxTy()));
6438 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6439 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6440 return std::make_pair(Lo, Hi);
6443 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6444 unsigned GlobalAddressSDNode::getAddressSpace() const {
6445 return getGlobal()->getType()->getAddressSpace();
6449 Type *ConstantPoolSDNode::getType() const {
6450 if (isMachineConstantPoolEntry())
6451 return Val.MachineCPVal->getType();
6452 return Val.ConstVal->getType();
6455 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6457 unsigned &SplatBitSize,
6459 unsigned MinSplatBits,
6461 EVT VT = getValueType(0);
6462 assert(VT.isVector() && "Expected a vector type");
6463 unsigned sz = VT.getSizeInBits();
6464 if (MinSplatBits > sz)
6467 SplatValue = APInt(sz, 0);
6468 SplatUndef = APInt(sz, 0);
6470 // Get the bits. Bits with undefined values (when the corresponding element
6471 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6472 // in SplatValue. If any of the values are not constant, give up and return
6474 unsigned int nOps = getNumOperands();
6475 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6476 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6478 for (unsigned j = 0; j < nOps; ++j) {
6479 unsigned i = isBigEndian ? nOps-1-j : j;
6480 SDValue OpVal = getOperand(i);
6481 unsigned BitPos = j * EltBitSize;
6483 if (OpVal.getOpcode() == ISD::UNDEF)
6484 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6485 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6486 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6487 zextOrTrunc(sz) << BitPos;
6488 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6489 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6494 // The build_vector is all constants or undefs. Find the smallest element
6495 // size that splats the vector.
6497 HasAnyUndefs = (SplatUndef != 0);
6500 unsigned HalfSize = sz / 2;
6501 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6502 APInt LowValue = SplatValue.trunc(HalfSize);
6503 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6504 APInt LowUndef = SplatUndef.trunc(HalfSize);
6506 // If the two halves do not match (ignoring undef bits), stop here.
6507 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6508 MinSplatBits > HalfSize)
6511 SplatValue = HighValue | LowValue;
6512 SplatUndef = HighUndef & LowUndef;
6521 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6522 // Find the first non-undef value in the shuffle mask.
6524 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6527 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6529 // Make sure all remaining elements are either undef or the same as the first
6531 for (int Idx = Mask[i]; i != e; ++i)
6532 if (Mask[i] >= 0 && Mask[i] != Idx)
6538 static void checkForCyclesHelper(const SDNode *N,
6539 SmallPtrSet<const SDNode*, 32> &Visited,
6540 SmallPtrSet<const SDNode*, 32> &Checked) {
6541 // If this node has already been checked, don't check it again.
6542 if (Checked.count(N))
6545 // If a node has already been visited on this depth-first walk, reject it as
6547 if (!Visited.insert(N)) {
6548 dbgs() << "Offending node:\n";
6550 errs() << "Detected cycle in SelectionDAG\n";
6554 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6555 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6562 void llvm::checkForCycles(const llvm::SDNode *N) {
6564 assert(N && "Checking nonexistent SDNode");
6565 SmallPtrSet<const SDNode*, 32> visited;
6566 SmallPtrSet<const SDNode*, 32> checked;
6567 checkForCyclesHelper(N, visited, checked);
6571 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6572 checkForCycles(DAG->getRoot().getNode());