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/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.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 while (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 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// isScalarToVector - Return true if the specified node is a
200 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
201 /// element is not an undef.
202 bool ISD::isScalarToVector(const SDNode *N) {
203 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
206 if (N->getOpcode() != ISD::BUILD_VECTOR)
208 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
210 unsigned NumElems = N->getNumOperands();
213 for (unsigned i = 1; i < NumElems; ++i) {
214 SDValue V = N->getOperand(i);
215 if (V.getOpcode() != ISD::UNDEF)
221 /// allOperandsUndef - Return true if the node has at least one operand
222 /// and all operands of the specified node are ISD::UNDEF.
223 bool ISD::allOperandsUndef(const SDNode *N) {
224 // Return false if the node has no operands.
225 // This is "logically inconsistent" with the definition of "all" but
226 // is probably the desired behavior.
227 if (N->getNumOperands() == 0)
230 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
231 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
237 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
240 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
242 return ISD::SIGN_EXTEND;
244 return ISD::ZERO_EXTEND;
249 llvm_unreachable("Invalid LoadExtType");
252 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
253 /// when given the operation for (X op Y).
254 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
255 // To perform this operation, we just need to swap the L and G bits of the
257 unsigned OldL = (Operation >> 2) & 1;
258 unsigned OldG = (Operation >> 1) & 1;
259 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
260 (OldL << 1) | // New G bit
261 (OldG << 2)); // New L bit.
264 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
265 /// 'op' is a valid SetCC operation.
266 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
267 unsigned Operation = Op;
269 Operation ^= 7; // Flip L, G, E bits, but not U.
271 Operation ^= 15; // Flip all of the condition bits.
273 if (Operation > ISD::SETTRUE2)
274 Operation &= ~8; // Don't let N and U bits get set.
276 return ISD::CondCode(Operation);
280 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
281 /// signed operation and 2 if the result is an unsigned comparison. Return zero
282 /// if the operation does not depend on the sign of the input (setne and seteq).
283 static int isSignedOp(ISD::CondCode Opcode) {
285 default: llvm_unreachable("Illegal integer setcc operation!");
287 case ISD::SETNE: return 0;
291 case ISD::SETGE: return 1;
295 case ISD::SETUGE: return 2;
299 /// getSetCCOrOperation - Return the result of a logical OR between different
300 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
301 /// returns SETCC_INVALID if it is not possible to represent the resultant
303 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
305 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
306 // Cannot fold a signed integer setcc with an unsigned integer setcc.
307 return ISD::SETCC_INVALID;
309 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
311 // If the N and U bits get set then the resultant comparison DOES suddenly
312 // care about orderedness, and is true when ordered.
313 if (Op > ISD::SETTRUE2)
314 Op &= ~16; // Clear the U bit if the N bit is set.
316 // Canonicalize illegal integer setcc's.
317 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
320 return ISD::CondCode(Op);
323 /// getSetCCAndOperation - Return the result of a logical AND between different
324 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
325 /// function returns zero if it is not possible to represent the resultant
327 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
329 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
330 // Cannot fold a signed setcc with an unsigned setcc.
331 return ISD::SETCC_INVALID;
333 // Combine all of the condition bits.
334 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
336 // Canonicalize illegal integer setcc's.
340 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
341 case ISD::SETOEQ: // SETEQ & SETU[LG]E
342 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
343 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
344 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
351 //===----------------------------------------------------------------------===//
352 // SDNode Profile Support
353 //===----------------------------------------------------------------------===//
355 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
357 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
361 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
362 /// solely with their pointer.
363 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
364 ID.AddPointer(VTList.VTs);
367 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
369 static void AddNodeIDOperands(FoldingSetNodeID &ID,
370 ArrayRef<SDValue> Ops) {
371 for (auto& Op : Ops) {
372 ID.AddPointer(Op.getNode());
373 ID.AddInteger(Op.getResNo());
377 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
379 static void AddNodeIDOperands(FoldingSetNodeID &ID,
380 ArrayRef<SDUse> Ops) {
381 for (auto& Op : Ops) {
382 ID.AddPointer(Op.getNode());
383 ID.AddInteger(Op.getResNo());
387 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
391 ID.AddBoolean(exact);
394 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
395 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
396 bool nuw, bool nsw, bool exact) {
397 if (isBinOpWithFlags(Opcode))
398 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
401 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
402 SDVTList VTList, ArrayRef<SDValue> OpList) {
403 AddNodeIDOpcode(ID, OpC);
404 AddNodeIDValueTypes(ID, VTList);
405 AddNodeIDOperands(ID, OpList);
408 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
410 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
411 switch (N->getOpcode()) {
412 case ISD::TargetExternalSymbol:
413 case ISD::ExternalSymbol:
414 llvm_unreachable("Should only be used on nodes with operands");
415 default: break; // Normal nodes don't need extra info.
416 case ISD::TargetConstant:
417 case ISD::Constant: {
418 const ConstantSDNode *C = cast<ConstantSDNode>(N);
419 ID.AddPointer(C->getConstantIntValue());
420 ID.AddBoolean(C->isOpaque());
423 case ISD::TargetConstantFP:
424 case ISD::ConstantFP: {
425 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
428 case ISD::TargetGlobalAddress:
429 case ISD::GlobalAddress:
430 case ISD::TargetGlobalTLSAddress:
431 case ISD::GlobalTLSAddress: {
432 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
433 ID.AddPointer(GA->getGlobal());
434 ID.AddInteger(GA->getOffset());
435 ID.AddInteger(GA->getTargetFlags());
436 ID.AddInteger(GA->getAddressSpace());
439 case ISD::BasicBlock:
440 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
443 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
445 case ISD::RegisterMask:
446 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
449 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
451 case ISD::FrameIndex:
452 case ISD::TargetFrameIndex:
453 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
456 case ISD::TargetJumpTable:
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
458 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
460 case ISD::ConstantPool:
461 case ISD::TargetConstantPool: {
462 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
463 ID.AddInteger(CP->getAlignment());
464 ID.AddInteger(CP->getOffset());
465 if (CP->isMachineConstantPoolEntry())
466 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
468 ID.AddPointer(CP->getConstVal());
469 ID.AddInteger(CP->getTargetFlags());
472 case ISD::TargetIndex: {
473 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
474 ID.AddInteger(TI->getIndex());
475 ID.AddInteger(TI->getOffset());
476 ID.AddInteger(TI->getTargetFlags());
480 const LoadSDNode *LD = cast<LoadSDNode>(N);
481 ID.AddInteger(LD->getMemoryVT().getRawBits());
482 ID.AddInteger(LD->getRawSubclassData());
483 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
487 const StoreSDNode *ST = cast<StoreSDNode>(N);
488 ID.AddInteger(ST->getMemoryVT().getRawBits());
489 ID.AddInteger(ST->getRawSubclassData());
490 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
501 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
502 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
503 BinNode->hasNoSignedWrap(), BinNode->isExact());
506 case ISD::ATOMIC_CMP_SWAP:
507 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
508 case ISD::ATOMIC_SWAP:
509 case ISD::ATOMIC_LOAD_ADD:
510 case ISD::ATOMIC_LOAD_SUB:
511 case ISD::ATOMIC_LOAD_AND:
512 case ISD::ATOMIC_LOAD_OR:
513 case ISD::ATOMIC_LOAD_XOR:
514 case ISD::ATOMIC_LOAD_NAND:
515 case ISD::ATOMIC_LOAD_MIN:
516 case ISD::ATOMIC_LOAD_MAX:
517 case ISD::ATOMIC_LOAD_UMIN:
518 case ISD::ATOMIC_LOAD_UMAX:
519 case ISD::ATOMIC_LOAD:
520 case ISD::ATOMIC_STORE: {
521 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
522 ID.AddInteger(AT->getMemoryVT().getRawBits());
523 ID.AddInteger(AT->getRawSubclassData());
524 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
527 case ISD::PREFETCH: {
528 const MemSDNode *PF = cast<MemSDNode>(N);
529 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
532 case ISD::VECTOR_SHUFFLE: {
533 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
534 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
536 ID.AddInteger(SVN->getMaskElt(i));
539 case ISD::TargetBlockAddress:
540 case ISD::BlockAddress: {
541 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
542 ID.AddPointer(BA->getBlockAddress());
543 ID.AddInteger(BA->getOffset());
544 ID.AddInteger(BA->getTargetFlags());
547 } // end switch (N->getOpcode())
549 // Target specific memory nodes could also have address spaces to check.
550 if (N->isTargetMemoryOpcode())
551 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
554 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
556 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
557 AddNodeIDOpcode(ID, N->getOpcode());
558 // Add the return value info.
559 AddNodeIDValueTypes(ID, N->getVTList());
560 // Add the operand info.
561 AddNodeIDOperands(ID, N->ops());
563 // Handle SDNode leafs with special info.
564 AddNodeIDCustom(ID, N);
567 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
568 /// the CSE map that carries volatility, temporalness, indexing mode, and
569 /// extension/truncation information.
571 static inline unsigned
572 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
573 bool isNonTemporal, bool isInvariant) {
574 assert((ConvType & 3) == ConvType &&
575 "ConvType may not require more than 2 bits!");
576 assert((AM & 7) == AM &&
577 "AM may not require more than 3 bits!");
581 (isNonTemporal << 6) |
585 //===----------------------------------------------------------------------===//
586 // SelectionDAG Class
587 //===----------------------------------------------------------------------===//
589 /// doNotCSE - Return true if CSE should not be performed for this node.
590 static bool doNotCSE(SDNode *N) {
591 if (N->getValueType(0) == MVT::Glue)
592 return true; // Never CSE anything that produces a flag.
594 switch (N->getOpcode()) {
596 case ISD::HANDLENODE:
598 return true; // Never CSE these nodes.
601 // Check that remaining values produced are not flags.
602 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
603 if (N->getValueType(i) == MVT::Glue)
604 return true; // Never CSE anything that produces a flag.
609 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
611 void SelectionDAG::RemoveDeadNodes() {
612 // Create a dummy node (which is not added to allnodes), that adds a reference
613 // to the root node, preventing it from being deleted.
614 HandleSDNode Dummy(getRoot());
616 SmallVector<SDNode*, 128> DeadNodes;
618 // Add all obviously-dead nodes to the DeadNodes worklist.
619 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
621 DeadNodes.push_back(I);
623 RemoveDeadNodes(DeadNodes);
625 // If the root changed (e.g. it was a dead load, update the root).
626 setRoot(Dummy.getValue());
629 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
630 /// given list, and any nodes that become unreachable as a result.
631 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
633 // Process the worklist, deleting the nodes and adding their uses to the
635 while (!DeadNodes.empty()) {
636 SDNode *N = DeadNodes.pop_back_val();
638 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
639 DUL->NodeDeleted(N, nullptr);
641 // Take the node out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Next, brutally remove the operand list. This is safe to do, as there are
645 // no cycles in the graph.
646 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
648 SDNode *Operand = Use.getNode();
651 // Now that we removed this operand, see if there are no uses of it left.
652 if (Operand->use_empty())
653 DeadNodes.push_back(Operand);
660 void SelectionDAG::RemoveDeadNode(SDNode *N){
661 SmallVector<SDNode*, 16> DeadNodes(1, N);
663 // Create a dummy node that adds a reference to the root node, preventing
664 // it from being deleted. (This matters if the root is an operand of the
666 HandleSDNode Dummy(getRoot());
668 RemoveDeadNodes(DeadNodes);
671 void SelectionDAG::DeleteNode(SDNode *N) {
672 // First take this out of the appropriate CSE map.
673 RemoveNodeFromCSEMaps(N);
675 // Finally, remove uses due to operands of this node, remove from the
676 // AllNodes list, and delete the node.
677 DeleteNodeNotInCSEMaps(N);
680 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
681 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
682 assert(N->use_empty() && "Cannot delete a node that is not dead!");
684 // Drop all of the operands and decrement used node's use counts.
690 void SDDbgInfo::erase(const SDNode *Node) {
691 DbgValMapType::iterator I = DbgValMap.find(Node);
692 if (I == DbgValMap.end())
694 for (auto &Val: I->second)
695 Val->setIsInvalidated();
699 void SelectionDAG::DeallocateNode(SDNode *N) {
700 if (N->OperandsNeedDelete)
701 delete[] N->OperandList;
703 // Set the opcode to DELETED_NODE to help catch bugs when node
704 // memory is reallocated.
705 N->NodeType = ISD::DELETED_NODE;
707 NodeAllocator.Deallocate(AllNodes.remove(N));
709 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
710 // them and forget about that node.
715 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
716 static void VerifySDNode(SDNode *N) {
717 switch (N->getOpcode()) {
720 case ISD::BUILD_PAIR: {
721 EVT VT = N->getValueType(0);
722 assert(N->getNumValues() == 1 && "Too many results!");
723 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
724 "Wrong return type!");
725 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
726 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
727 "Mismatched operand types!");
728 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
729 "Wrong operand type!");
730 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
731 "Wrong return type size");
734 case ISD::BUILD_VECTOR: {
735 assert(N->getNumValues() == 1 && "Too many results!");
736 assert(N->getValueType(0).isVector() && "Wrong return type!");
737 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
738 "Wrong number of operands!");
739 EVT EltVT = N->getValueType(0).getVectorElementType();
740 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
741 assert((I->getValueType() == EltVT ||
742 (EltVT.isInteger() && I->getValueType().isInteger() &&
743 EltVT.bitsLE(I->getValueType()))) &&
744 "Wrong operand type!");
745 assert(I->getValueType() == N->getOperand(0).getValueType() &&
746 "Operands must all have the same type");
754 /// \brief Insert a newly allocated node into the DAG.
756 /// Handles insertion into the all nodes list and CSE map, as well as
757 /// verification and other common operations when a new node is allocated.
758 void SelectionDAG::InsertNode(SDNode *N) {
759 AllNodes.push_back(N);
765 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
766 /// correspond to it. This is useful when we're about to delete or repurpose
767 /// the node. We don't want future request for structurally identical nodes
768 /// to return N anymore.
769 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
771 switch (N->getOpcode()) {
772 case ISD::HANDLENODE: return false; // noop.
774 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
775 "Cond code doesn't exist!");
776 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
777 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
779 case ISD::ExternalSymbol:
780 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
782 case ISD::TargetExternalSymbol: {
783 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
784 Erased = TargetExternalSymbols.erase(
785 std::pair<std::string,unsigned char>(ESN->getSymbol(),
786 ESN->getTargetFlags()));
789 case ISD::VALUETYPE: {
790 EVT VT = cast<VTSDNode>(N)->getVT();
791 if (VT.isExtended()) {
792 Erased = ExtendedValueTypeNodes.erase(VT);
794 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
795 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
800 // Remove it from the CSE Map.
801 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
802 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
803 Erased = CSEMap.RemoveNode(N);
807 // Verify that the node was actually in one of the CSE maps, unless it has a
808 // flag result (which cannot be CSE'd) or is one of the special cases that are
809 // not subject to CSE.
810 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
811 !N->isMachineOpcode() && !doNotCSE(N)) {
814 llvm_unreachable("Node is not in map!");
820 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
821 /// maps and modified in place. Add it back to the CSE maps, unless an identical
822 /// node already exists, in which case transfer all its users to the existing
823 /// node. This transfer can potentially trigger recursive merging.
826 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
827 // For node types that aren't CSE'd, just act as if no identical node
830 SDNode *Existing = CSEMap.GetOrInsertNode(N);
832 // If there was already an existing matching node, use ReplaceAllUsesWith
833 // to replace the dead one with the existing one. This can cause
834 // recursive merging of other unrelated nodes down the line.
835 ReplaceAllUsesWith(N, Existing);
837 // N is now dead. Inform the listeners and delete it.
838 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
839 DUL->NodeDeleted(N, Existing);
840 DeleteNodeNotInCSEMaps(N);
845 // If the node doesn't already exist, we updated it. Inform listeners.
846 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
850 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
851 /// were replaced with those specified. If this node is never memoized,
852 /// return null, otherwise return a pointer to the slot it would take. If a
853 /// node already exists with these operands, the slot will be non-null.
854 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
859 SDValue Ops[] = { Op };
861 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
862 AddNodeIDCustom(ID, N);
863 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
867 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
868 /// were replaced with those specified. If this node is never memoized,
869 /// return null, otherwise return a pointer to the slot it would take. If a
870 /// node already exists with these operands, the slot will be non-null.
871 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
872 SDValue Op1, SDValue Op2,
877 SDValue Ops[] = { Op1, Op2 };
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
886 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
887 /// were replaced with those specified. If this node is never memoized,
888 /// return null, otherwise return a pointer to the slot it would take. If a
889 /// node already exists with these operands, the slot will be non-null.
890 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
896 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
897 AddNodeIDCustom(ID, N);
898 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
902 /// getEVTAlignment - Compute the default alignment value for the
905 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
906 Type *Ty = VT == MVT::iPTR ?
907 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
908 VT.getTypeForEVT(*getContext());
910 return TLI->getDataLayout()->getABITypeAlignment(Ty);
913 // EntryNode could meaningfully have debug info if we can find it...
914 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
915 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
916 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
917 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
918 UpdateListeners(nullptr) {
919 AllNodes.push_back(&EntryNode);
920 DbgInfo = new SDDbgInfo();
923 void SelectionDAG::init(MachineFunction &mf) {
925 TLI = getSubtarget().getTargetLowering();
926 TSI = getSubtarget().getSelectionDAGInfo();
927 Context = &mf.getFunction()->getContext();
930 SelectionDAG::~SelectionDAG() {
931 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
936 void SelectionDAG::allnodes_clear() {
937 assert(&*AllNodes.begin() == &EntryNode);
938 AllNodes.remove(AllNodes.begin());
939 while (!AllNodes.empty())
940 DeallocateNode(AllNodes.begin());
943 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
944 SDVTList VTs, SDValue N1,
945 SDValue N2, bool nuw, bool nsw,
947 if (isBinOpWithFlags(Opcode)) {
948 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
949 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
950 FN->setHasNoUnsignedWrap(nuw);
951 FN->setHasNoSignedWrap(nsw);
952 FN->setIsExact(exact);
957 BinarySDNode *N = new (NodeAllocator)
958 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
962 void SelectionDAG::clear() {
964 OperandAllocator.Reset();
967 ExtendedValueTypeNodes.clear();
968 ExternalSymbols.clear();
969 TargetExternalSymbols.clear();
970 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
971 static_cast<CondCodeSDNode*>(nullptr));
972 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
973 static_cast<SDNode*>(nullptr));
975 EntryNode.UseList = nullptr;
976 AllNodes.push_back(&EntryNode);
977 Root = getEntryNode();
981 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
982 return VT.bitsGT(Op.getValueType()) ?
983 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
984 getNode(ISD::TRUNCATE, DL, VT, Op);
987 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
988 return VT.bitsGT(Op.getValueType()) ?
989 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
990 getNode(ISD::TRUNCATE, DL, VT, Op);
993 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
994 return VT.bitsGT(Op.getValueType()) ?
995 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
996 getNode(ISD::TRUNCATE, DL, VT, Op);
999 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1001 if (VT.bitsLE(Op.getValueType()))
1002 return getNode(ISD::TRUNCATE, SL, VT, Op);
1004 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1005 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1008 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1009 assert(!VT.isVector() &&
1010 "getZeroExtendInReg should use the vector element type instead of "
1011 "the vector type!");
1012 if (Op.getValueType() == VT) return Op;
1013 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1014 APInt Imm = APInt::getLowBitsSet(BitWidth,
1015 VT.getSizeInBits());
1016 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1017 getConstant(Imm, Op.getValueType()));
1020 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1021 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1022 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1023 "The sizes of the input and result must match in order to perform the "
1024 "extend in-register.");
1025 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1026 "The destination vector type must have fewer lanes than the input.");
1027 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1030 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1031 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1032 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1033 "The sizes of the input and result must match in order to perform the "
1034 "extend in-register.");
1035 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1036 "The destination vector type must have fewer lanes than the input.");
1037 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1040 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1041 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1042 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1043 "The sizes of the input and result must match in order to perform the "
1044 "extend in-register.");
1045 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1046 "The destination vector type must have fewer lanes than the input.");
1047 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1050 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1052 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1053 EVT EltVT = VT.getScalarType();
1055 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1056 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1059 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1060 EVT EltVT = VT.getScalarType();
1062 switch (TLI->getBooleanContents(VT)) {
1063 case TargetLowering::ZeroOrOneBooleanContent:
1064 case TargetLowering::UndefinedBooleanContent:
1065 TrueValue = getConstant(1, VT);
1067 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1068 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1072 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1075 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1076 EVT EltVT = VT.getScalarType();
1077 assert((EltVT.getSizeInBits() >= 64 ||
1078 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1079 "getConstant with a uint64_t value that doesn't fit in the type!");
1080 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1083 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1085 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1088 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1090 assert(VT.isInteger() && "Cannot create FP integer constant!");
1092 EVT EltVT = VT.getScalarType();
1093 const ConstantInt *Elt = &Val;
1095 // In some cases the vector type is legal but the element type is illegal and
1096 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1097 // inserted value (the type does not need to match the vector element type).
1098 // Any extra bits introduced will be truncated away.
1099 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1100 TargetLowering::TypePromoteInteger) {
1101 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1102 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1103 Elt = ConstantInt::get(*getContext(), NewVal);
1105 // In other cases the element type is illegal and needs to be expanded, for
1106 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1107 // the value into n parts and use a vector type with n-times the elements.
1108 // Then bitcast to the type requested.
1109 // Legalizing constants too early makes the DAGCombiner's job harder so we
1110 // only legalize if the DAG tells us we must produce legal types.
1111 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1112 TLI->getTypeAction(*getContext(), EltVT) ==
1113 TargetLowering::TypeExpandInteger) {
1114 APInt NewVal = Elt->getValue();
1115 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1116 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1117 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1118 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1120 // Check the temporary vector is the correct size. If this fails then
1121 // getTypeToTransformTo() probably returned a type whose size (in bits)
1122 // isn't a power-of-2 factor of the requested type size.
1123 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1125 SmallVector<SDValue, 2> EltParts;
1126 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1127 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1128 .trunc(ViaEltSizeInBits),
1129 ViaEltVT, isT, isO));
1132 // EltParts is currently in little endian order. If we actually want
1133 // big-endian order then reverse it now.
1134 if (TLI->isBigEndian())
1135 std::reverse(EltParts.begin(), EltParts.end());
1137 // The elements must be reversed when the element order is different
1138 // to the endianness of the elements (because the BITCAST is itself a
1139 // vector shuffle in this situation). However, we do not need any code to
1140 // perform this reversal because getConstant() is producing a vector
1142 // This situation occurs in MIPS MSA.
1144 SmallVector<SDValue, 8> Ops;
1145 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1146 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1148 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1149 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1154 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1155 "APInt size does not match type size!");
1156 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1157 FoldingSetNodeID ID;
1158 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1162 SDNode *N = nullptr;
1163 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1165 return SDValue(N, 0);
1168 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1169 CSEMap.InsertNode(N, IP);
1173 SDValue Result(N, 0);
1174 if (VT.isVector()) {
1175 SmallVector<SDValue, 8> Ops;
1176 Ops.assign(VT.getVectorNumElements(), Result);
1177 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1182 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1183 return getConstant(Val, TLI->getPointerTy(), isTarget);
1187 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1188 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1191 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1192 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1194 EVT EltVT = VT.getScalarType();
1196 // Do the map lookup using the actual bit pattern for the floating point
1197 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1198 // we don't have issues with SNANs.
1199 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1200 FoldingSetNodeID ID;
1201 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1204 SDNode *N = nullptr;
1205 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1207 return SDValue(N, 0);
1210 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1211 CSEMap.InsertNode(N, IP);
1215 SDValue Result(N, 0);
1216 if (VT.isVector()) {
1217 SmallVector<SDValue, 8> Ops;
1218 Ops.assign(VT.getVectorNumElements(), Result);
1219 // FIXME SDLoc info might be appropriate here
1220 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1225 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1226 EVT EltVT = VT.getScalarType();
1227 if (EltVT==MVT::f32)
1228 return getConstantFP(APFloat((float)Val), VT, isTarget);
1229 else if (EltVT==MVT::f64)
1230 return getConstantFP(APFloat(Val), VT, isTarget);
1231 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1234 APFloat apf = APFloat(Val);
1235 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1237 return getConstantFP(apf, VT, isTarget);
1239 llvm_unreachable("Unsupported type in getConstantFP");
1242 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1243 EVT VT, int64_t Offset,
1245 unsigned char TargetFlags) {
1246 assert((TargetFlags == 0 || isTargetGA) &&
1247 "Cannot set target flags on target-independent globals");
1249 // Truncate (with sign-extension) the offset value to the pointer size.
1250 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1252 Offset = SignExtend64(Offset, BitWidth);
1255 if (GV->isThreadLocal())
1256 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1258 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1260 FoldingSetNodeID ID;
1261 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1263 ID.AddInteger(Offset);
1264 ID.AddInteger(TargetFlags);
1265 ID.AddInteger(GV->getType()->getAddressSpace());
1267 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268 return SDValue(E, 0);
1270 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1271 DL.getDebugLoc(), GV, VT,
1272 Offset, TargetFlags);
1273 CSEMap.InsertNode(N, IP);
1275 return SDValue(N, 0);
1278 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1279 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1280 FoldingSetNodeID ID;
1281 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1284 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1285 return SDValue(E, 0);
1287 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1288 CSEMap.InsertNode(N, IP);
1290 return SDValue(N, 0);
1293 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1294 unsigned char TargetFlags) {
1295 assert((TargetFlags == 0 || isTarget) &&
1296 "Cannot set target flags on target-independent jump tables");
1297 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1298 FoldingSetNodeID ID;
1299 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1301 ID.AddInteger(TargetFlags);
1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304 return SDValue(E, 0);
1306 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1308 CSEMap.InsertNode(N, IP);
1310 return SDValue(N, 0);
1313 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1314 unsigned Alignment, int Offset,
1316 unsigned char TargetFlags) {
1317 assert((TargetFlags == 0 || isTarget) &&
1318 "Cannot set target flags on target-independent globals");
1320 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1321 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1322 FoldingSetNodeID ID;
1323 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1324 ID.AddInteger(Alignment);
1325 ID.AddInteger(Offset);
1327 ID.AddInteger(TargetFlags);
1329 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1330 return SDValue(E, 0);
1332 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1333 Alignment, TargetFlags);
1334 CSEMap.InsertNode(N, IP);
1336 return SDValue(N, 0);
1340 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1341 unsigned Alignment, int Offset,
1343 unsigned char TargetFlags) {
1344 assert((TargetFlags == 0 || isTarget) &&
1345 "Cannot set target flags on target-independent globals");
1347 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1348 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1349 FoldingSetNodeID ID;
1350 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1351 ID.AddInteger(Alignment);
1352 ID.AddInteger(Offset);
1353 C->addSelectionDAGCSEId(ID);
1354 ID.AddInteger(TargetFlags);
1356 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1357 return SDValue(E, 0);
1359 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1360 Alignment, TargetFlags);
1361 CSEMap.InsertNode(N, IP);
1363 return SDValue(N, 0);
1366 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1367 unsigned char TargetFlags) {
1368 FoldingSetNodeID ID;
1369 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1370 ID.AddInteger(Index);
1371 ID.AddInteger(Offset);
1372 ID.AddInteger(TargetFlags);
1374 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1375 return SDValue(E, 0);
1377 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1379 CSEMap.InsertNode(N, IP);
1381 return SDValue(N, 0);
1384 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1385 FoldingSetNodeID ID;
1386 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1389 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1390 return SDValue(E, 0);
1392 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1393 CSEMap.InsertNode(N, IP);
1395 return SDValue(N, 0);
1398 SDValue SelectionDAG::getValueType(EVT VT) {
1399 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1400 ValueTypeNodes.size())
1401 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1403 SDNode *&N = VT.isExtended() ?
1404 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1406 if (N) return SDValue(N, 0);
1407 N = new (NodeAllocator) VTSDNode(VT);
1409 return SDValue(N, 0);
1412 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1413 SDNode *&N = ExternalSymbols[Sym];
1414 if (N) return SDValue(N, 0);
1415 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1417 return SDValue(N, 0);
1420 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1421 unsigned char TargetFlags) {
1423 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1425 if (N) return SDValue(N, 0);
1426 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1428 return SDValue(N, 0);
1431 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1432 if ((unsigned)Cond >= CondCodeNodes.size())
1433 CondCodeNodes.resize(Cond+1);
1435 if (!CondCodeNodes[Cond]) {
1436 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1437 CondCodeNodes[Cond] = N;
1441 return SDValue(CondCodeNodes[Cond], 0);
1444 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1445 // the shuffle mask M that point at N1 to point at N2, and indices that point
1446 // N2 to point at N1.
1447 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1449 int NElts = M.size();
1450 for (int i = 0; i != NElts; ++i) {
1458 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1459 SDValue N2, const int *Mask) {
1460 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1461 "Invalid VECTOR_SHUFFLE");
1463 // Canonicalize shuffle undef, undef -> undef
1464 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1465 return getUNDEF(VT);
1467 // Validate that all indices in Mask are within the range of the elements
1468 // input to the shuffle.
1469 unsigned NElts = VT.getVectorNumElements();
1470 SmallVector<int, 8> MaskVec;
1471 for (unsigned i = 0; i != NElts; ++i) {
1472 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1473 MaskVec.push_back(Mask[i]);
1476 // Canonicalize shuffle v, v -> v, undef
1479 for (unsigned i = 0; i != NElts; ++i)
1480 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1483 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1484 if (N1.getOpcode() == ISD::UNDEF)
1485 commuteShuffle(N1, N2, MaskVec);
1487 // Canonicalize all index into lhs, -> shuffle lhs, undef
1488 // Canonicalize all index into rhs, -> shuffle rhs, undef
1489 bool AllLHS = true, AllRHS = true;
1490 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1491 for (unsigned i = 0; i != NElts; ++i) {
1492 if (MaskVec[i] >= (int)NElts) {
1497 } else if (MaskVec[i] >= 0) {
1501 if (AllLHS && AllRHS)
1502 return getUNDEF(VT);
1503 if (AllLHS && !N2Undef)
1507 commuteShuffle(N1, N2, MaskVec);
1509 // Reset our undef status after accounting for the mask.
1510 N2Undef = N2.getOpcode() == ISD::UNDEF;
1511 // Re-check whether both sides ended up undef.
1512 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1513 return getUNDEF(VT);
1515 // If Identity shuffle return that node.
1516 bool Identity = true, AllSame = true;
1517 for (unsigned i = 0; i != NElts; ++i) {
1518 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1519 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1521 if (Identity && NElts)
1524 // Shuffling a constant splat doesn't change the result.
1528 // Look through any bitcasts. We check that these don't change the number
1529 // (and size) of elements and just changes their types.
1530 while (V.getOpcode() == ISD::BITCAST)
1531 V = V->getOperand(0);
1533 // A splat should always show up as a build vector node.
1534 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1535 BitVector UndefElements;
1536 SDValue Splat = BV->getSplatValue(&UndefElements);
1537 // If this is a splat of an undef, shuffling it is also undef.
1538 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1539 return getUNDEF(VT);
1542 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1544 // We only have a splat which can skip shuffles if there is a splatted
1545 // value and no undef lanes rearranged by the shuffle.
1546 if (Splat && UndefElements.none()) {
1547 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1548 // number of elements match or the value splatted is a zero constant.
1551 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1552 if (C->isNullValue())
1556 // If the shuffle itself creates a constant splat, build the vector
1558 if (AllSame && SameNumElts) {
1559 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1560 if (isa<ConstantSDNode>(Splatted) || isa<ConstantFPSDNode>(Splatted)) {
1561 SmallVector<SDValue, 8> Ops;
1562 for (unsigned i = 0; i != NElts; ++i)
1563 Ops.push_back(Splatted);
1566 getNode(ISD::BUILD_VECTOR, dl, BV->getValueType(0), Ops);
1568 // We may have jumped through bitcasts, so the type of the
1569 // BUILD_VECTOR may not match the type of the shuffle.
1570 if (BV->getValueType(0) != VT)
1571 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1578 FoldingSetNodeID ID;
1579 SDValue Ops[2] = { N1, N2 };
1580 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1581 for (unsigned i = 0; i != NElts; ++i)
1582 ID.AddInteger(MaskVec[i]);
1585 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1586 return SDValue(E, 0);
1588 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1589 // SDNode doesn't have access to it. This memory will be "leaked" when
1590 // the node is deallocated, but recovered when the NodeAllocator is released.
1591 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1592 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1594 ShuffleVectorSDNode *N =
1595 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1596 dl.getDebugLoc(), N1, N2,
1598 CSEMap.InsertNode(N, IP);
1600 return SDValue(N, 0);
1603 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1604 MVT VT = SV.getSimpleValueType(0);
1605 unsigned NumElems = VT.getVectorNumElements();
1606 SmallVector<int, 8> MaskVec;
1608 for (unsigned i = 0; i != NumElems; ++i) {
1609 int Idx = SV.getMaskElt(i);
1611 if (Idx < (int)NumElems)
1616 MaskVec.push_back(Idx);
1619 SDValue Op0 = SV.getOperand(0);
1620 SDValue Op1 = SV.getOperand(1);
1621 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1624 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1625 SDValue Val, SDValue DTy,
1626 SDValue STy, SDValue Rnd, SDValue Sat,
1627 ISD::CvtCode Code) {
1628 // If the src and dest types are the same and the conversion is between
1629 // integer types of the same sign or two floats, no conversion is necessary.
1631 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1634 FoldingSetNodeID ID;
1635 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1636 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1638 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1639 return SDValue(E, 0);
1641 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1644 CSEMap.InsertNode(N, IP);
1646 return SDValue(N, 0);
1649 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1650 FoldingSetNodeID ID;
1651 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1652 ID.AddInteger(RegNo);
1654 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1655 return SDValue(E, 0);
1657 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1658 CSEMap.InsertNode(N, IP);
1660 return SDValue(N, 0);
1663 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1664 FoldingSetNodeID ID;
1665 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1666 ID.AddPointer(RegMask);
1668 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1669 return SDValue(E, 0);
1671 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1672 CSEMap.InsertNode(N, IP);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1678 FoldingSetNodeID ID;
1679 SDValue Ops[] = { Root };
1680 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1681 ID.AddPointer(Label);
1683 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1684 return SDValue(E, 0);
1686 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1687 dl.getDebugLoc(), Root, Label);
1688 CSEMap.InsertNode(N, IP);
1690 return SDValue(N, 0);
1694 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1697 unsigned char TargetFlags) {
1698 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1700 FoldingSetNodeID ID;
1701 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1703 ID.AddInteger(Offset);
1704 ID.AddInteger(TargetFlags);
1706 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1707 return SDValue(E, 0);
1709 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1711 CSEMap.InsertNode(N, IP);
1713 return SDValue(N, 0);
1716 SDValue SelectionDAG::getSrcValue(const Value *V) {
1717 assert((!V || V->getType()->isPointerTy()) &&
1718 "SrcValue is not a pointer?");
1720 FoldingSetNodeID ID;
1721 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1725 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1726 return SDValue(E, 0);
1728 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1729 CSEMap.InsertNode(N, IP);
1731 return SDValue(N, 0);
1734 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1735 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1736 FoldingSetNodeID ID;
1737 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1741 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1742 return SDValue(E, 0);
1744 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1745 CSEMap.InsertNode(N, IP);
1747 return SDValue(N, 0);
1750 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1751 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1752 unsigned SrcAS, unsigned DestAS) {
1753 SDValue Ops[] = {Ptr};
1754 FoldingSetNodeID ID;
1755 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1756 ID.AddInteger(SrcAS);
1757 ID.AddInteger(DestAS);
1760 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1761 return SDValue(E, 0);
1763 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1765 VT, Ptr, SrcAS, DestAS);
1766 CSEMap.InsertNode(N, IP);
1768 return SDValue(N, 0);
1771 /// getShiftAmountOperand - Return the specified value casted to
1772 /// the target's desired shift amount type.
1773 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1774 EVT OpTy = Op.getValueType();
1775 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1776 if (OpTy == ShTy || OpTy.isVector()) return Op;
1778 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1779 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1782 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1783 /// specified value type.
1784 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1785 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1786 unsigned ByteSize = VT.getStoreSize();
1787 Type *Ty = VT.getTypeForEVT(*getContext());
1788 unsigned StackAlign =
1789 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1791 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1792 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1795 /// CreateStackTemporary - Create a stack temporary suitable for holding
1796 /// either of the specified value types.
1797 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1798 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1799 VT2.getStoreSizeInBits())/8;
1800 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1801 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1802 const DataLayout *TD = TLI->getDataLayout();
1803 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1804 TD->getPrefTypeAlignment(Ty2));
1806 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1807 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1808 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1811 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1812 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1813 // These setcc operations always fold.
1817 case ISD::SETFALSE2: return getConstant(0, VT);
1819 case ISD::SETTRUE2: {
1820 TargetLowering::BooleanContent Cnt =
1821 TLI->getBooleanContents(N1->getValueType(0));
1823 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1836 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1840 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1841 const APInt &C2 = N2C->getAPIntValue();
1842 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1843 const APInt &C1 = N1C->getAPIntValue();
1846 default: llvm_unreachable("Unknown integer setcc!");
1847 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1848 case ISD::SETNE: return getConstant(C1 != C2, VT);
1849 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1850 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1851 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1852 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1853 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1854 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1855 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1856 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1860 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1861 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1862 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1865 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1866 return getUNDEF(VT);
1868 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1869 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1870 return getUNDEF(VT);
1872 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1873 R==APFloat::cmpLessThan, VT);
1874 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1875 return getUNDEF(VT);
1877 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1878 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1879 return getUNDEF(VT);
1881 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1882 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1883 return getUNDEF(VT);
1885 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1886 R==APFloat::cmpEqual, VT);
1887 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1888 return getUNDEF(VT);
1890 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1891 R==APFloat::cmpEqual, VT);
1892 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1893 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1894 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1895 R==APFloat::cmpEqual, VT);
1896 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1897 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1898 R==APFloat::cmpLessThan, VT);
1899 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1900 R==APFloat::cmpUnordered, VT);
1901 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1902 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1905 // Ensure that the constant occurs on the RHS.
1906 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1907 MVT CompVT = N1.getValueType().getSimpleVT();
1908 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1911 return getSetCC(dl, VT, N2, N1, SwappedCond);
1915 // Could not fold it.
1919 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1920 /// use this predicate to simplify operations downstream.
1921 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1922 // This predicate is not safe for vector operations.
1923 if (Op.getValueType().isVector())
1926 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1927 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1930 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1931 /// this predicate to simplify operations downstream. Mask is known to be zero
1932 /// for bits that V cannot have.
1933 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1934 unsigned Depth) const {
1935 APInt KnownZero, KnownOne;
1936 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1937 return (KnownZero & Mask) == Mask;
1940 /// Determine which bits of Op are known to be either zero or one and return
1941 /// them in the KnownZero/KnownOne bitsets.
1942 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1943 APInt &KnownOne, unsigned Depth) const {
1944 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1946 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1948 return; // Limit search depth.
1950 APInt KnownZero2, KnownOne2;
1952 switch (Op.getOpcode()) {
1954 // We know all of the bits for a constant!
1955 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1956 KnownZero = ~KnownOne;
1959 // If either the LHS or the RHS are Zero, the result is zero.
1960 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1961 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1963 // Output known-1 bits are only known if set in both the LHS & RHS.
1964 KnownOne &= KnownOne2;
1965 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1966 KnownZero |= KnownZero2;
1969 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1970 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1972 // Output known-0 bits are only known if clear in both the LHS & RHS.
1973 KnownZero &= KnownZero2;
1974 // Output known-1 are known to be set if set in either the LHS | RHS.
1975 KnownOne |= KnownOne2;
1978 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1979 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1981 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1982 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1983 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1984 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1985 KnownZero = KnownZeroOut;
1989 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1990 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1992 // If low bits are zero in either operand, output low known-0 bits.
1993 // Also compute a conserative estimate for high known-0 bits.
1994 // More trickiness is possible, but this is sufficient for the
1995 // interesting case of alignment computation.
1996 KnownOne.clearAllBits();
1997 unsigned TrailZ = KnownZero.countTrailingOnes() +
1998 KnownZero2.countTrailingOnes();
1999 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2000 KnownZero2.countLeadingOnes(),
2001 BitWidth) - BitWidth;
2003 TrailZ = std::min(TrailZ, BitWidth);
2004 LeadZ = std::min(LeadZ, BitWidth);
2005 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2006 APInt::getHighBitsSet(BitWidth, LeadZ);
2010 // For the purposes of computing leading zeros we can conservatively
2011 // treat a udiv as a logical right shift by the power of 2 known to
2012 // be less than the denominator.
2013 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2014 unsigned LeadZ = KnownZero2.countLeadingOnes();
2016 KnownOne2.clearAllBits();
2017 KnownZero2.clearAllBits();
2018 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2019 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2020 if (RHSUnknownLeadingOnes != BitWidth)
2021 LeadZ = std::min(BitWidth,
2022 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2024 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2028 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2029 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2031 // Only known if known in both the LHS and RHS.
2032 KnownOne &= KnownOne2;
2033 KnownZero &= KnownZero2;
2035 case ISD::SELECT_CC:
2036 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2037 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2039 // Only known if known in both the LHS and RHS.
2040 KnownOne &= KnownOne2;
2041 KnownZero &= KnownZero2;
2049 if (Op.getResNo() != 1)
2051 // The boolean result conforms to getBooleanContents.
2052 // If we know the result of a setcc has the top bits zero, use this info.
2053 // We know that we have an integer-based boolean since these operations
2054 // are only available for integer.
2055 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2056 TargetLowering::ZeroOrOneBooleanContent &&
2058 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2061 // If we know the result of a setcc has the top bits zero, use this info.
2062 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2063 TargetLowering::ZeroOrOneBooleanContent &&
2065 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2068 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2069 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2070 unsigned ShAmt = SA->getZExtValue();
2072 // If the shift count is an invalid immediate, don't do anything.
2073 if (ShAmt >= BitWidth)
2076 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2077 KnownZero <<= ShAmt;
2079 // low bits known zero.
2080 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2084 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2085 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2086 unsigned ShAmt = SA->getZExtValue();
2088 // If the shift count is an invalid immediate, don't do anything.
2089 if (ShAmt >= BitWidth)
2092 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2093 KnownZero = KnownZero.lshr(ShAmt);
2094 KnownOne = KnownOne.lshr(ShAmt);
2096 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2097 KnownZero |= HighBits; // High bits known zero.
2101 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2102 unsigned ShAmt = SA->getZExtValue();
2104 // If the shift count is an invalid immediate, don't do anything.
2105 if (ShAmt >= BitWidth)
2108 // If any of the demanded bits are produced by the sign extension, we also
2109 // demand the input sign bit.
2110 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2112 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2113 KnownZero = KnownZero.lshr(ShAmt);
2114 KnownOne = KnownOne.lshr(ShAmt);
2116 // Handle the sign bits.
2117 APInt SignBit = APInt::getSignBit(BitWidth);
2118 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2120 if (KnownZero.intersects(SignBit)) {
2121 KnownZero |= HighBits; // New bits are known zero.
2122 } else if (KnownOne.intersects(SignBit)) {
2123 KnownOne |= HighBits; // New bits are known one.
2127 case ISD::SIGN_EXTEND_INREG: {
2128 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2129 unsigned EBits = EVT.getScalarType().getSizeInBits();
2131 // Sign extension. Compute the demanded bits in the result that are not
2132 // present in the input.
2133 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2135 APInt InSignBit = APInt::getSignBit(EBits);
2136 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2138 // If the sign extended bits are demanded, we know that the sign
2140 InSignBit = InSignBit.zext(BitWidth);
2141 if (NewBits.getBoolValue())
2142 InputDemandedBits |= InSignBit;
2144 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2145 KnownOne &= InputDemandedBits;
2146 KnownZero &= InputDemandedBits;
2148 // If the sign bit of the input is known set or clear, then we know the
2149 // top bits of the result.
2150 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2151 KnownZero |= NewBits;
2152 KnownOne &= ~NewBits;
2153 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2154 KnownOne |= NewBits;
2155 KnownZero &= ~NewBits;
2156 } else { // Input sign bit unknown
2157 KnownZero &= ~NewBits;
2158 KnownOne &= ~NewBits;
2163 case ISD::CTTZ_ZERO_UNDEF:
2165 case ISD::CTLZ_ZERO_UNDEF:
2167 unsigned LowBits = Log2_32(BitWidth)+1;
2168 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2169 KnownOne.clearAllBits();
2173 LoadSDNode *LD = cast<LoadSDNode>(Op);
2174 // If this is a ZEXTLoad and we are looking at the loaded value.
2175 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2176 EVT VT = LD->getMemoryVT();
2177 unsigned MemBits = VT.getScalarType().getSizeInBits();
2178 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2179 } else if (const MDNode *Ranges = LD->getRanges()) {
2180 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2184 case ISD::ZERO_EXTEND: {
2185 EVT InVT = Op.getOperand(0).getValueType();
2186 unsigned InBits = InVT.getScalarType().getSizeInBits();
2187 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2188 KnownZero = KnownZero.trunc(InBits);
2189 KnownOne = KnownOne.trunc(InBits);
2190 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2191 KnownZero = KnownZero.zext(BitWidth);
2192 KnownOne = KnownOne.zext(BitWidth);
2193 KnownZero |= NewBits;
2196 case ISD::SIGN_EXTEND: {
2197 EVT InVT = Op.getOperand(0).getValueType();
2198 unsigned InBits = InVT.getScalarType().getSizeInBits();
2199 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2201 KnownZero = KnownZero.trunc(InBits);
2202 KnownOne = KnownOne.trunc(InBits);
2203 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2205 // Note if the sign bit is known to be zero or one.
2206 bool SignBitKnownZero = KnownZero.isNegative();
2207 bool SignBitKnownOne = KnownOne.isNegative();
2209 KnownZero = KnownZero.zext(BitWidth);
2210 KnownOne = KnownOne.zext(BitWidth);
2212 // If the sign bit is known zero or one, the top bits match.
2213 if (SignBitKnownZero)
2214 KnownZero |= NewBits;
2215 else if (SignBitKnownOne)
2216 KnownOne |= NewBits;
2219 case ISD::ANY_EXTEND: {
2220 EVT InVT = Op.getOperand(0).getValueType();
2221 unsigned InBits = InVT.getScalarType().getSizeInBits();
2222 KnownZero = KnownZero.trunc(InBits);
2223 KnownOne = KnownOne.trunc(InBits);
2224 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2225 KnownZero = KnownZero.zext(BitWidth);
2226 KnownOne = KnownOne.zext(BitWidth);
2229 case ISD::TRUNCATE: {
2230 EVT InVT = Op.getOperand(0).getValueType();
2231 unsigned InBits = InVT.getScalarType().getSizeInBits();
2232 KnownZero = KnownZero.zext(InBits);
2233 KnownOne = KnownOne.zext(InBits);
2234 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2235 KnownZero = KnownZero.trunc(BitWidth);
2236 KnownOne = KnownOne.trunc(BitWidth);
2239 case ISD::AssertZext: {
2240 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2241 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2242 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2243 KnownZero |= (~InMask);
2244 KnownOne &= (~KnownZero);
2248 // All bits are zero except the low bit.
2249 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2253 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2254 // We know that the top bits of C-X are clear if X contains less bits
2255 // than C (i.e. no wrap-around can happen). For example, 20-X is
2256 // positive if we can prove that X is >= 0 and < 16.
2257 if (CLHS->getAPIntValue().isNonNegative()) {
2258 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2259 // NLZ can't be BitWidth with no sign bit
2260 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2261 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2263 // If all of the MaskV bits are known to be zero, then we know the
2264 // output top bits are zero, because we now know that the output is
2266 if ((KnownZero2 & MaskV) == MaskV) {
2267 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2268 // Top bits known zero.
2269 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2277 // Output known-0 bits are known if clear or set in both the low clear bits
2278 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2279 // low 3 bits clear.
2280 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2281 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2283 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2284 KnownZeroOut = std::min(KnownZeroOut,
2285 KnownZero2.countTrailingOnes());
2287 if (Op.getOpcode() == ISD::ADD) {
2288 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2292 // With ADDE, a carry bit may be added in, so we can only use this
2293 // information if we know (at least) that the low two bits are clear. We
2294 // then return to the caller that the low bit is unknown but that other bits
2296 if (KnownZeroOut >= 2) // ADDE
2297 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2301 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2302 const APInt &RA = Rem->getAPIntValue().abs();
2303 if (RA.isPowerOf2()) {
2304 APInt LowBits = RA - 1;
2305 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2307 // The low bits of the first operand are unchanged by the srem.
2308 KnownZero = KnownZero2 & LowBits;
2309 KnownOne = KnownOne2 & LowBits;
2311 // If the first operand is non-negative or has all low bits zero, then
2312 // the upper bits are all zero.
2313 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2314 KnownZero |= ~LowBits;
2316 // If the first operand is negative and not all low bits are zero, then
2317 // the upper bits are all one.
2318 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2319 KnownOne |= ~LowBits;
2320 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2325 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2326 const APInt &RA = Rem->getAPIntValue();
2327 if (RA.isPowerOf2()) {
2328 APInt LowBits = (RA - 1);
2329 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2331 // The upper bits are all zero, the lower ones are unchanged.
2332 KnownZero = KnownZero2 | ~LowBits;
2333 KnownOne = KnownOne2 & LowBits;
2338 // Since the result is less than or equal to either operand, any leading
2339 // zero bits in either operand must also exist in the result.
2340 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2341 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2343 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2344 KnownZero2.countLeadingOnes());
2345 KnownOne.clearAllBits();
2346 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2349 case ISD::EXTRACT_ELEMENT: {
2350 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2351 const unsigned Index =
2352 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2353 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2355 // Remove low part of known bits mask
2356 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2357 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2359 // Remove high part of known bit mask
2360 KnownZero = KnownZero.trunc(BitWidth);
2361 KnownOne = KnownOne.trunc(BitWidth);
2364 case ISD::FrameIndex:
2365 case ISD::TargetFrameIndex:
2366 if (unsigned Align = InferPtrAlignment(Op)) {
2367 // The low bits are known zero if the pointer is aligned.
2368 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2374 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2377 case ISD::INTRINSIC_WO_CHAIN:
2378 case ISD::INTRINSIC_W_CHAIN:
2379 case ISD::INTRINSIC_VOID:
2380 // Allow the target to implement this method for its nodes.
2381 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2385 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2388 /// ComputeNumSignBits - Return the number of times the sign bit of the
2389 /// register is replicated into the other bits. We know that at least 1 bit
2390 /// is always equal to the sign bit (itself), but other cases can give us
2391 /// information. For example, immediately after an "SRA X, 2", we know that
2392 /// the top 3 bits are all equal to each other, so we return 3.
2393 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2394 EVT VT = Op.getValueType();
2395 assert(VT.isInteger() && "Invalid VT!");
2396 unsigned VTBits = VT.getScalarType().getSizeInBits();
2398 unsigned FirstAnswer = 1;
2401 return 1; // Limit search depth.
2403 switch (Op.getOpcode()) {
2405 case ISD::AssertSext:
2406 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2407 return VTBits-Tmp+1;
2408 case ISD::AssertZext:
2409 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2412 case ISD::Constant: {
2413 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2414 return Val.getNumSignBits();
2417 case ISD::SIGN_EXTEND:
2419 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2420 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2422 case ISD::SIGN_EXTEND_INREG:
2423 // Max of the input and what this extends.
2425 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2428 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2429 return std::max(Tmp, Tmp2);
2432 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2433 // SRA X, C -> adds C sign bits.
2434 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2435 Tmp += C->getZExtValue();
2436 if (Tmp > VTBits) Tmp = VTBits;
2440 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2441 // shl destroys sign bits.
2442 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2443 if (C->getZExtValue() >= VTBits || // Bad shift.
2444 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2445 return Tmp - C->getZExtValue();
2450 case ISD::XOR: // NOT is handled here.
2451 // Logical binary ops preserve the number of sign bits at the worst.
2452 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2454 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2455 FirstAnswer = std::min(Tmp, Tmp2);
2456 // We computed what we know about the sign bits as our first
2457 // answer. Now proceed to the generic code that uses
2458 // computeKnownBits, and pick whichever answer is better.
2463 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2464 if (Tmp == 1) return 1; // Early out.
2465 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2466 return std::min(Tmp, Tmp2);
2474 if (Op.getResNo() != 1)
2476 // The boolean result conforms to getBooleanContents. Fall through.
2477 // If setcc returns 0/-1, all bits are sign bits.
2478 // We know that we have an integer-based boolean since these operations
2479 // are only available for integer.
2480 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2481 TargetLowering::ZeroOrNegativeOneBooleanContent)
2485 // If setcc returns 0/-1, all bits are sign bits.
2486 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2487 TargetLowering::ZeroOrNegativeOneBooleanContent)
2492 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2493 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2495 // Handle rotate right by N like a rotate left by 32-N.
2496 if (Op.getOpcode() == ISD::ROTR)
2497 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2499 // If we aren't rotating out all of the known-in sign bits, return the
2500 // number that are left. This handles rotl(sext(x), 1) for example.
2501 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2502 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2506 // Add can have at most one carry bit. Thus we know that the output
2507 // is, at worst, one more bit than the inputs.
2508 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2509 if (Tmp == 1) return 1; // Early out.
2511 // Special case decrementing a value (ADD X, -1):
2512 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2513 if (CRHS->isAllOnesValue()) {
2514 APInt KnownZero, KnownOne;
2515 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2517 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2519 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2522 // If we are subtracting one from a positive number, there is no carry
2523 // out of the result.
2524 if (KnownZero.isNegative())
2528 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2529 if (Tmp2 == 1) return 1;
2530 return std::min(Tmp, Tmp2)-1;
2533 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2534 if (Tmp2 == 1) return 1;
2537 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2538 if (CLHS->isNullValue()) {
2539 APInt KnownZero, KnownOne;
2540 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2541 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2543 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2546 // If the input is known to be positive (the sign bit is known clear),
2547 // the output of the NEG has the same number of sign bits as the input.
2548 if (KnownZero.isNegative())
2551 // Otherwise, we treat this like a SUB.
2554 // Sub can have at most one carry bit. Thus we know that the output
2555 // is, at worst, one more bit than the inputs.
2556 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2557 if (Tmp == 1) return 1; // Early out.
2558 return std::min(Tmp, Tmp2)-1;
2560 // FIXME: it's tricky to do anything useful for this, but it is an important
2561 // case for targets like X86.
2563 case ISD::EXTRACT_ELEMENT: {
2564 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2565 const int BitWidth = Op.getValueType().getSizeInBits();
2567 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2569 // Get reverse index (starting from 1), Op1 value indexes elements from
2570 // little end. Sign starts at big end.
2571 const int rIndex = Items - 1 -
2572 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2574 // If the sign portion ends in our element the substraction gives correct
2575 // result. Otherwise it gives either negative or > bitwidth result
2576 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2580 // If we are looking at the loaded value of the SDNode.
2581 if (Op.getResNo() == 0) {
2582 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2583 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2584 unsigned ExtType = LD->getExtensionType();
2587 case ISD::SEXTLOAD: // '17' bits known
2588 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2589 return VTBits-Tmp+1;
2590 case ISD::ZEXTLOAD: // '16' bits known
2591 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2597 // Allow the target to implement this method for its nodes.
2598 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2599 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2600 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2601 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2602 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2603 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2606 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2607 // use this information.
2608 APInt KnownZero, KnownOne;
2609 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2612 if (KnownZero.isNegative()) { // sign bit is 0
2614 } else if (KnownOne.isNegative()) { // sign bit is 1;
2621 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2622 // the number of identical bits in the top of the input value.
2624 Mask <<= Mask.getBitWidth()-VTBits;
2625 // Return # leading zeros. We use 'min' here in case Val was zero before
2626 // shifting. We don't want to return '64' as for an i32 "0".
2627 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2630 /// isBaseWithConstantOffset - Return true if the specified operand is an
2631 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2632 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2633 /// semantics as an ADD. This handles the equivalence:
2634 /// X|Cst == X+Cst iff X&Cst = 0.
2635 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2636 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2637 !isa<ConstantSDNode>(Op.getOperand(1)))
2640 if (Op.getOpcode() == ISD::OR &&
2641 !MaskedValueIsZero(Op.getOperand(0),
2642 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2649 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2650 // If we're told that NaNs won't happen, assume they won't.
2651 if (getTarget().Options.NoNaNsFPMath)
2654 // If the value is a constant, we can obviously see if it is a NaN or not.
2655 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2656 return !C->getValueAPF().isNaN();
2658 // TODO: Recognize more cases here.
2663 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2664 // If the value is a constant, we can obviously see if it is a zero or not.
2665 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2666 return !C->isZero();
2668 // TODO: Recognize more cases here.
2669 switch (Op.getOpcode()) {
2672 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2673 return !C->isNullValue();
2680 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2681 // Check the obvious case.
2682 if (A == B) return true;
2684 // For for negative and positive zero.
2685 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2686 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2687 if (CA->isZero() && CB->isZero()) return true;
2689 // Otherwise they may not be equal.
2693 /// getNode - Gets or creates the specified node.
2695 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2696 FoldingSetNodeID ID;
2697 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2699 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2700 return SDValue(E, 0);
2702 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2703 DL.getDebugLoc(), getVTList(VT));
2704 CSEMap.InsertNode(N, IP);
2707 return SDValue(N, 0);
2710 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2711 EVT VT, SDValue Operand) {
2712 // Constant fold unary operations with an integer constant operand. Even
2713 // opaque constant will be folded, because the folding of unary operations
2714 // doesn't create new constants with different values. Nevertheless, the
2715 // opaque flag is preserved during folding to prevent future folding with
2717 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2718 const APInt &Val = C->getAPIntValue();
2721 case ISD::SIGN_EXTEND:
2722 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2723 C->isTargetOpcode(), C->isOpaque());
2724 case ISD::ANY_EXTEND:
2725 case ISD::ZERO_EXTEND:
2727 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2728 C->isTargetOpcode(), C->isOpaque());
2729 case ISD::UINT_TO_FP:
2730 case ISD::SINT_TO_FP: {
2731 APFloat apf(EVTToAPFloatSemantics(VT),
2732 APInt::getNullValue(VT.getSizeInBits()));
2733 (void)apf.convertFromAPInt(Val,
2734 Opcode==ISD::SINT_TO_FP,
2735 APFloat::rmNearestTiesToEven);
2736 return getConstantFP(apf, VT);
2739 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2740 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2741 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2742 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2743 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2744 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2747 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2750 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2753 case ISD::CTLZ_ZERO_UNDEF:
2754 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2757 case ISD::CTTZ_ZERO_UNDEF:
2758 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2763 // Constant fold unary operations with a floating point constant operand.
2764 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2765 APFloat V = C->getValueAPF(); // make copy
2769 return getConstantFP(V, VT);
2772 return getConstantFP(V, VT);
2774 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2775 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2776 return getConstantFP(V, VT);
2780 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2781 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2782 return getConstantFP(V, VT);
2786 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2787 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2788 return getConstantFP(V, VT);
2791 case ISD::FP_EXTEND: {
2793 // This can return overflow, underflow, or inexact; we don't care.
2794 // FIXME need to be more flexible about rounding mode.
2795 (void)V.convert(EVTToAPFloatSemantics(VT),
2796 APFloat::rmNearestTiesToEven, &ignored);
2797 return getConstantFP(V, VT);
2799 case ISD::FP_TO_SINT:
2800 case ISD::FP_TO_UINT: {
2803 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2804 // FIXME need to be more flexible about rounding mode.
2805 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2806 Opcode==ISD::FP_TO_SINT,
2807 APFloat::rmTowardZero, &ignored);
2808 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2810 APInt api(VT.getSizeInBits(), x);
2811 return getConstant(api, VT);
2814 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2815 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2816 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2817 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2818 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2819 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2824 // Constant fold unary operations with a vector integer operand.
2825 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2826 if (BV->isConstant()) {
2829 // FIXME: Entirely reasonable to perform folding of other unary
2830 // operations here as the need arises.
2832 case ISD::UINT_TO_FP:
2833 case ISD::SINT_TO_FP: {
2834 SmallVector<SDValue, 8> Ops;
2835 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2836 SDValue OpN = BV->getOperand(i);
2837 // Let the above scalar folding handle the conversion of each
2839 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2843 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2849 unsigned OpOpcode = Operand.getNode()->getOpcode();
2851 case ISD::TokenFactor:
2852 case ISD::MERGE_VALUES:
2853 case ISD::CONCAT_VECTORS:
2854 return Operand; // Factor, merge or concat of one node? No need.
2855 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2856 case ISD::FP_EXTEND:
2857 assert(VT.isFloatingPoint() &&
2858 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2859 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2860 assert((!VT.isVector() ||
2861 VT.getVectorNumElements() ==
2862 Operand.getValueType().getVectorNumElements()) &&
2863 "Vector element count mismatch!");
2864 if (Operand.getOpcode() == ISD::UNDEF)
2865 return getUNDEF(VT);
2867 case ISD::SIGN_EXTEND:
2868 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2869 "Invalid SIGN_EXTEND!");
2870 if (Operand.getValueType() == VT) return Operand; // noop extension
2871 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2872 "Invalid sext node, dst < src!");
2873 assert((!VT.isVector() ||
2874 VT.getVectorNumElements() ==
2875 Operand.getValueType().getVectorNumElements()) &&
2876 "Vector element count mismatch!");
2877 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2878 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2879 else if (OpOpcode == ISD::UNDEF)
2880 // sext(undef) = 0, because the top bits will all be the same.
2881 return getConstant(0, VT);
2883 case ISD::ZERO_EXTEND:
2884 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2885 "Invalid ZERO_EXTEND!");
2886 if (Operand.getValueType() == VT) return Operand; // noop extension
2887 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2888 "Invalid zext node, dst < src!");
2889 assert((!VT.isVector() ||
2890 VT.getVectorNumElements() ==
2891 Operand.getValueType().getVectorNumElements()) &&
2892 "Vector element count mismatch!");
2893 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2894 return getNode(ISD::ZERO_EXTEND, DL, VT,
2895 Operand.getNode()->getOperand(0));
2896 else if (OpOpcode == ISD::UNDEF)
2897 // zext(undef) = 0, because the top bits will be zero.
2898 return getConstant(0, VT);
2900 case ISD::ANY_EXTEND:
2901 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2902 "Invalid ANY_EXTEND!");
2903 if (Operand.getValueType() == VT) return Operand; // noop extension
2904 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2905 "Invalid anyext node, dst < src!");
2906 assert((!VT.isVector() ||
2907 VT.getVectorNumElements() ==
2908 Operand.getValueType().getVectorNumElements()) &&
2909 "Vector element count mismatch!");
2911 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2912 OpOpcode == ISD::ANY_EXTEND)
2913 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2914 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2915 else if (OpOpcode == ISD::UNDEF)
2916 return getUNDEF(VT);
2918 // (ext (trunx x)) -> x
2919 if (OpOpcode == ISD::TRUNCATE) {
2920 SDValue OpOp = Operand.getNode()->getOperand(0);
2921 if (OpOp.getValueType() == VT)
2926 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2927 "Invalid TRUNCATE!");
2928 if (Operand.getValueType() == VT) return Operand; // noop truncate
2929 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2930 "Invalid truncate node, src < dst!");
2931 assert((!VT.isVector() ||
2932 VT.getVectorNumElements() ==
2933 Operand.getValueType().getVectorNumElements()) &&
2934 "Vector element count mismatch!");
2935 if (OpOpcode == ISD::TRUNCATE)
2936 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2937 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2938 OpOpcode == ISD::ANY_EXTEND) {
2939 // If the source is smaller than the dest, we still need an extend.
2940 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2941 .bitsLT(VT.getScalarType()))
2942 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2943 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2944 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2945 return Operand.getNode()->getOperand(0);
2947 if (OpOpcode == ISD::UNDEF)
2948 return getUNDEF(VT);
2951 // Basic sanity checking.
2952 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2953 && "Cannot BITCAST between types of different sizes!");
2954 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2955 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2956 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2957 if (OpOpcode == ISD::UNDEF)
2958 return getUNDEF(VT);
2960 case ISD::SCALAR_TO_VECTOR:
2961 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2962 (VT.getVectorElementType() == Operand.getValueType() ||
2963 (VT.getVectorElementType().isInteger() &&
2964 Operand.getValueType().isInteger() &&
2965 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2966 "Illegal SCALAR_TO_VECTOR node!");
2967 if (OpOpcode == ISD::UNDEF)
2968 return getUNDEF(VT);
2969 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2970 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2971 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2972 Operand.getConstantOperandVal(1) == 0 &&
2973 Operand.getOperand(0).getValueType() == VT)
2974 return Operand.getOperand(0);
2977 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2978 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2979 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2980 Operand.getNode()->getOperand(0));
2981 if (OpOpcode == ISD::FNEG) // --X -> X
2982 return Operand.getNode()->getOperand(0);
2985 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2986 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2991 SDVTList VTs = getVTList(VT);
2992 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2993 FoldingSetNodeID ID;
2994 SDValue Ops[1] = { Operand };
2995 AddNodeIDNode(ID, Opcode, VTs, Ops);
2997 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2998 return SDValue(E, 0);
3000 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3001 DL.getDebugLoc(), VTs, Operand);
3002 CSEMap.InsertNode(N, IP);
3004 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3005 DL.getDebugLoc(), VTs, Operand);
3009 return SDValue(N, 0);
3012 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3013 SDNode *Cst1, SDNode *Cst2) {
3014 // If the opcode is a target-specific ISD node, there's nothing we can
3015 // do here and the operand rules may not line up with the below, so
3017 if (Opcode >= ISD::BUILTIN_OP_END)
3020 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3021 SmallVector<SDValue, 4> Outputs;
3022 EVT SVT = VT.getScalarType();
3024 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3025 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3026 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3029 if (Scalar1 && Scalar2)
3030 // Scalar instruction.
3031 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3033 // For vectors extract each constant element into Inputs so we can constant
3034 // fold them individually.
3035 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3036 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3040 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3042 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3043 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3044 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3045 if (!V1 || !V2) // Not a constant, bail.
3048 if (V1->isOpaque() || V2->isOpaque())
3051 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3052 // FIXME: This is valid and could be handled by truncating the APInts.
3053 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3056 Inputs.push_back(std::make_pair(V1, V2));
3060 // We have a number of constant values, constant fold them element by element.
3061 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3062 const APInt &C1 = Inputs[I].first->getAPIntValue();
3063 const APInt &C2 = Inputs[I].second->getAPIntValue();
3067 Outputs.push_back(getConstant(C1 + C2, SVT));
3070 Outputs.push_back(getConstant(C1 - C2, SVT));
3073 Outputs.push_back(getConstant(C1 * C2, SVT));
3076 if (!C2.getBoolValue())
3078 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3081 if (!C2.getBoolValue())
3083 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3086 if (!C2.getBoolValue())
3088 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3091 if (!C2.getBoolValue())
3093 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3096 Outputs.push_back(getConstant(C1 & C2, SVT));
3099 Outputs.push_back(getConstant(C1 | C2, SVT));
3102 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3105 Outputs.push_back(getConstant(C1 << C2, SVT));
3108 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3111 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3114 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3117 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3124 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3125 "Expected a scalar or vector!"));
3127 // Handle the scalar case first.
3129 return Outputs.back();
3131 // We may have a vector type but a scalar result. Create a splat.
3132 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3134 // Build a big vector out of the scalar elements we generated.
3135 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3138 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3139 SDValue N2, bool nuw, bool nsw, bool exact) {
3140 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3141 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3144 case ISD::TokenFactor:
3145 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3146 N2.getValueType() == MVT::Other && "Invalid token factor!");
3147 // Fold trivial token factors.
3148 if (N1.getOpcode() == ISD::EntryToken) return N2;
3149 if (N2.getOpcode() == ISD::EntryToken) return N1;
3150 if (N1 == N2) return N1;
3152 case ISD::CONCAT_VECTORS:
3153 // Concat of UNDEFs is UNDEF.
3154 if (N1.getOpcode() == ISD::UNDEF &&
3155 N2.getOpcode() == ISD::UNDEF)
3156 return getUNDEF(VT);
3158 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3159 // one big BUILD_VECTOR.
3160 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3161 N2.getOpcode() == ISD::BUILD_VECTOR) {
3162 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3163 N1.getNode()->op_end());
3164 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3165 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3169 assert(VT.isInteger() && "This operator does not apply to FP types!");
3170 assert(N1.getValueType() == N2.getValueType() &&
3171 N1.getValueType() == VT && "Binary operator types must match!");
3172 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3173 // worth handling here.
3174 if (N2C && N2C->isNullValue())
3176 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3183 assert(VT.isInteger() && "This operator does not apply to FP types!");
3184 assert(N1.getValueType() == N2.getValueType() &&
3185 N1.getValueType() == VT && "Binary operator types must match!");
3186 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3187 // it's worth handling here.
3188 if (N2C && N2C->isNullValue())
3198 assert(VT.isInteger() && "This operator does not apply to FP types!");
3199 assert(N1.getValueType() == N2.getValueType() &&
3200 N1.getValueType() == VT && "Binary operator types must match!");
3207 if (getTarget().Options.UnsafeFPMath) {
3208 if (Opcode == ISD::FADD) {
3210 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3211 if (CFP->getValueAPF().isZero())
3214 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3215 if (CFP->getValueAPF().isZero())
3217 } else if (Opcode == ISD::FSUB) {
3219 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3220 if (CFP->getValueAPF().isZero())
3222 } else if (Opcode == ISD::FMUL) {
3223 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3226 // If the first operand isn't the constant, try the second
3228 CFP = dyn_cast<ConstantFPSDNode>(N2);
3235 return SDValue(CFP,0);
3237 if (CFP->isExactlyValue(1.0))
3242 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3243 assert(N1.getValueType() == N2.getValueType() &&
3244 N1.getValueType() == VT && "Binary operator types must match!");
3246 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3247 assert(N1.getValueType() == VT &&
3248 N1.getValueType().isFloatingPoint() &&
3249 N2.getValueType().isFloatingPoint() &&
3250 "Invalid FCOPYSIGN!");
3257 assert(VT == N1.getValueType() &&
3258 "Shift operators return type must be the same as their first arg");
3259 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3260 "Shifts only work on integers");
3261 assert((!VT.isVector() || VT == N2.getValueType()) &&
3262 "Vector shift amounts must be in the same as their first arg");
3263 // Verify that the shift amount VT is bit enough to hold valid shift
3264 // amounts. This catches things like trying to shift an i1024 value by an
3265 // i8, which is easy to fall into in generic code that uses
3266 // TLI.getShiftAmount().
3267 assert(N2.getValueType().getSizeInBits() >=
3268 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3269 "Invalid use of small shift amount with oversized value!");
3271 // Always fold shifts of i1 values so the code generator doesn't need to
3272 // handle them. Since we know the size of the shift has to be less than the
3273 // size of the value, the shift/rotate count is guaranteed to be zero.
3276 if (N2C && N2C->isNullValue())
3279 case ISD::FP_ROUND_INREG: {
3280 EVT EVT = cast<VTSDNode>(N2)->getVT();
3281 assert(VT == N1.getValueType() && "Not an inreg round!");
3282 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3283 "Cannot FP_ROUND_INREG integer types");
3284 assert(EVT.isVector() == VT.isVector() &&
3285 "FP_ROUND_INREG type should be vector iff the operand "
3287 assert((!EVT.isVector() ||
3288 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3289 "Vector element counts must match in FP_ROUND_INREG");
3290 assert(EVT.bitsLE(VT) && "Not rounding down!");
3292 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3296 assert(VT.isFloatingPoint() &&
3297 N1.getValueType().isFloatingPoint() &&
3298 VT.bitsLE(N1.getValueType()) &&
3299 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3300 if (N1.getValueType() == VT) return N1; // noop conversion.
3302 case ISD::AssertSext:
3303 case ISD::AssertZext: {
3304 EVT EVT = cast<VTSDNode>(N2)->getVT();
3305 assert(VT == N1.getValueType() && "Not an inreg extend!");
3306 assert(VT.isInteger() && EVT.isInteger() &&
3307 "Cannot *_EXTEND_INREG FP types");
3308 assert(!EVT.isVector() &&
3309 "AssertSExt/AssertZExt type should be the vector element type "
3310 "rather than the vector type!");
3311 assert(EVT.bitsLE(VT) && "Not extending!");
3312 if (VT == EVT) return N1; // noop assertion.
3315 case ISD::SIGN_EXTEND_INREG: {
3316 EVT EVT = cast<VTSDNode>(N2)->getVT();
3317 assert(VT == N1.getValueType() && "Not an inreg extend!");
3318 assert(VT.isInteger() && EVT.isInteger() &&
3319 "Cannot *_EXTEND_INREG FP types");
3320 assert(EVT.isVector() == VT.isVector() &&
3321 "SIGN_EXTEND_INREG type should be vector iff the operand "
3323 assert((!EVT.isVector() ||
3324 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3325 "Vector element counts must match in SIGN_EXTEND_INREG");
3326 assert(EVT.bitsLE(VT) && "Not extending!");
3327 if (EVT == VT) return N1; // Not actually extending
3330 APInt Val = N1C->getAPIntValue();
3331 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3332 Val <<= Val.getBitWidth()-FromBits;
3333 Val = Val.ashr(Val.getBitWidth()-FromBits);
3334 return getConstant(Val, VT);
3338 case ISD::EXTRACT_VECTOR_ELT:
3339 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3340 if (N1.getOpcode() == ISD::UNDEF)
3341 return getUNDEF(VT);
3343 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3344 // expanding copies of large vectors from registers.
3346 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3347 N1.getNumOperands() > 0) {
3349 N1.getOperand(0).getValueType().getVectorNumElements();
3350 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3351 N1.getOperand(N2C->getZExtValue() / Factor),
3352 getConstant(N2C->getZExtValue() % Factor,
3353 N2.getValueType()));
3356 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3357 // expanding large vector constants.
3358 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3359 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3361 if (VT != Elt.getValueType())
3362 // If the vector element type is not legal, the BUILD_VECTOR operands
3363 // are promoted and implicitly truncated, and the result implicitly
3364 // extended. Make that explicit here.
3365 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3370 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3371 // operations are lowered to scalars.
3372 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3373 // If the indices are the same, return the inserted element else
3374 // if the indices are known different, extract the element from
3375 // the original vector.
3376 SDValue N1Op2 = N1.getOperand(2);
3377 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3379 if (N1Op2C && N2C) {
3380 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3381 if (VT == N1.getOperand(1).getValueType())
3382 return N1.getOperand(1);
3384 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3387 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3391 case ISD::EXTRACT_ELEMENT:
3392 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3393 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3394 (N1.getValueType().isInteger() == VT.isInteger()) &&
3395 N1.getValueType() != VT &&
3396 "Wrong types for EXTRACT_ELEMENT!");
3398 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3399 // 64-bit integers into 32-bit parts. Instead of building the extract of
3400 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3401 if (N1.getOpcode() == ISD::BUILD_PAIR)
3402 return N1.getOperand(N2C->getZExtValue());
3404 // EXTRACT_ELEMENT of a constant int is also very common.
3405 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3406 unsigned ElementSize = VT.getSizeInBits();
3407 unsigned Shift = ElementSize * N2C->getZExtValue();
3408 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3409 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3412 case ISD::EXTRACT_SUBVECTOR: {
3414 if (VT.isSimple() && N1.getValueType().isSimple()) {
3415 assert(VT.isVector() && N1.getValueType().isVector() &&
3416 "Extract subvector VTs must be a vectors!");
3417 assert(VT.getVectorElementType() ==
3418 N1.getValueType().getVectorElementType() &&
3419 "Extract subvector VTs must have the same element type!");
3420 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3421 "Extract subvector must be from larger vector to smaller vector!");
3423 if (isa<ConstantSDNode>(Index.getNode())) {
3424 assert((VT.getVectorNumElements() +
3425 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3426 <= N1.getValueType().getVectorNumElements())
3427 && "Extract subvector overflow!");
3430 // Trivial extraction.
3431 if (VT.getSimpleVT() == N1.getSimpleValueType())
3438 // Perform trivial constant folding.
3440 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3443 // Canonicalize constant to RHS if commutative.
3444 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3445 std::swap(N1C, N2C);
3449 // Constant fold FP operations.
3450 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3451 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3452 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3454 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3455 // Canonicalize constant to RHS if commutative.
3456 std::swap(N1CFP, N2CFP);
3459 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3460 APFloat::opStatus s;
3463 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3464 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3465 return getConstantFP(V1, VT);
3468 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3469 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3470 return getConstantFP(V1, VT);
3473 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3474 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3475 return getConstantFP(V1, VT);
3478 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3479 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3480 s!=APFloat::opDivByZero)) {
3481 return getConstantFP(V1, VT);
3485 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3486 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3487 s!=APFloat::opDivByZero)) {
3488 return getConstantFP(V1, VT);
3491 case ISD::FCOPYSIGN:
3493 return getConstantFP(V1, VT);
3498 if (Opcode == ISD::FP_ROUND) {
3499 APFloat V = N1CFP->getValueAPF(); // make copy
3501 // This can return overflow, underflow, or inexact; we don't care.
3502 // FIXME need to be more flexible about rounding mode.
3503 (void)V.convert(EVTToAPFloatSemantics(VT),
3504 APFloat::rmNearestTiesToEven, &ignored);
3505 return getConstantFP(V, VT);
3509 // Canonicalize an UNDEF to the RHS, even over a constant.
3510 if (N1.getOpcode() == ISD::UNDEF) {
3511 if (isCommutativeBinOp(Opcode)) {
3515 case ISD::FP_ROUND_INREG:
3516 case ISD::SIGN_EXTEND_INREG:
3522 return N1; // fold op(undef, arg2) -> undef
3530 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3531 // For vectors, we can't easily build an all zero vector, just return
3538 // Fold a bunch of operators when the RHS is undef.
3539 if (N2.getOpcode() == ISD::UNDEF) {
3542 if (N1.getOpcode() == ISD::UNDEF)
3543 // Handle undef ^ undef -> 0 special case. This is a common
3545 return getConstant(0, VT);
3555 return N2; // fold op(arg1, undef) -> undef
3561 if (getTarget().Options.UnsafeFPMath)
3569 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3570 // For vectors, we can't easily build an all zero vector, just return
3575 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3576 // For vectors, we can't easily build an all one vector, just return
3584 // Memoize this node if possible.
3586 SDVTList VTs = getVTList(VT);
3587 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3588 if (VT != MVT::Glue) {
3589 SDValue Ops[] = {N1, N2};
3590 FoldingSetNodeID ID;
3591 AddNodeIDNode(ID, Opcode, VTs, Ops);
3593 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3595 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3596 return SDValue(E, 0);
3598 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3600 CSEMap.InsertNode(N, IP);
3603 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3607 return SDValue(N, 0);
3610 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3611 SDValue N1, SDValue N2, SDValue N3) {
3612 // Perform various simplifications.
3613 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3616 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3617 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3618 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3619 if (N1CFP && N2CFP && N3CFP) {
3620 APFloat V1 = N1CFP->getValueAPF();
3621 const APFloat &V2 = N2CFP->getValueAPF();
3622 const APFloat &V3 = N3CFP->getValueAPF();
3623 APFloat::opStatus s =
3624 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3625 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3626 return getConstantFP(V1, VT);
3630 case ISD::CONCAT_VECTORS:
3631 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3632 // one big BUILD_VECTOR.
3633 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3634 N2.getOpcode() == ISD::BUILD_VECTOR &&
3635 N3.getOpcode() == ISD::BUILD_VECTOR) {
3636 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3637 N1.getNode()->op_end());
3638 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3639 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3640 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3644 // Use FoldSetCC to simplify SETCC's.
3645 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3646 if (Simp.getNode()) return Simp;
3651 if (N1C->getZExtValue())
3652 return N2; // select true, X, Y -> X
3653 return N3; // select false, X, Y -> Y
3656 if (N2 == N3) return N2; // select C, X, X -> X
3658 case ISD::VECTOR_SHUFFLE:
3659 llvm_unreachable("should use getVectorShuffle constructor!");
3660 case ISD::INSERT_SUBVECTOR: {
3662 if (VT.isSimple() && N1.getValueType().isSimple()
3663 && N2.getValueType().isSimple()) {
3664 assert(VT.isVector() && N1.getValueType().isVector() &&
3665 N2.getValueType().isVector() &&
3666 "Insert subvector VTs must be a vectors");
3667 assert(VT == N1.getValueType() &&
3668 "Dest and insert subvector source types must match!");
3669 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3670 "Insert subvector must be from smaller vector to larger vector!");
3671 if (isa<ConstantSDNode>(Index.getNode())) {
3672 assert((N2.getValueType().getVectorNumElements() +
3673 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3674 <= VT.getVectorNumElements())
3675 && "Insert subvector overflow!");
3678 // Trivial insertion.
3679 if (VT.getSimpleVT() == N2.getSimpleValueType())
3685 // Fold bit_convert nodes from a type to themselves.
3686 if (N1.getValueType() == VT)
3691 // Memoize node if it doesn't produce a flag.
3693 SDVTList VTs = getVTList(VT);
3694 if (VT != MVT::Glue) {
3695 SDValue Ops[] = { N1, N2, N3 };
3696 FoldingSetNodeID ID;
3697 AddNodeIDNode(ID, Opcode, VTs, Ops);
3699 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3700 return SDValue(E, 0);
3702 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3703 DL.getDebugLoc(), VTs, N1, N2, N3);
3704 CSEMap.InsertNode(N, IP);
3706 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3707 DL.getDebugLoc(), VTs, N1, N2, N3);
3711 return SDValue(N, 0);
3714 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3715 SDValue N1, SDValue N2, SDValue N3,
3717 SDValue Ops[] = { N1, N2, N3, N4 };
3718 return getNode(Opcode, DL, VT, Ops);
3721 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3722 SDValue N1, SDValue N2, SDValue N3,
3723 SDValue N4, SDValue N5) {
3724 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3725 return getNode(Opcode, DL, VT, Ops);
3728 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3729 /// the incoming stack arguments to be loaded from the stack.
3730 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3731 SmallVector<SDValue, 8> ArgChains;
3733 // Include the original chain at the beginning of the list. When this is
3734 // used by target LowerCall hooks, this helps legalize find the
3735 // CALLSEQ_BEGIN node.
3736 ArgChains.push_back(Chain);
3738 // Add a chain value for each stack argument.
3739 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3740 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3741 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3742 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3743 if (FI->getIndex() < 0)
3744 ArgChains.push_back(SDValue(L, 1));
3746 // Build a tokenfactor for all the chains.
3747 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3750 /// getMemsetValue - Vectorized representation of the memset value
3752 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3754 assert(Value.getOpcode() != ISD::UNDEF);
3756 unsigned NumBits = VT.getScalarType().getSizeInBits();
3757 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3758 assert(C->getAPIntValue().getBitWidth() == 8);
3759 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3761 return DAG.getConstant(Val, VT);
3762 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3765 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3767 // Use a multiplication with 0x010101... to extend the input to the
3769 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3770 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3776 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3777 /// used when a memcpy is turned into a memset when the source is a constant
3779 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3780 const TargetLowering &TLI, StringRef Str) {
3781 // Handle vector with all elements zero.
3784 return DAG.getConstant(0, VT);
3785 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3786 return DAG.getConstantFP(0.0, VT);
3787 else if (VT.isVector()) {
3788 unsigned NumElts = VT.getVectorNumElements();
3789 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3790 return DAG.getNode(ISD::BITCAST, dl, VT,
3791 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3794 llvm_unreachable("Expected type!");
3797 assert(!VT.isVector() && "Can't handle vector type here!");
3798 unsigned NumVTBits = VT.getSizeInBits();
3799 unsigned NumVTBytes = NumVTBits / 8;
3800 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3802 APInt Val(NumVTBits, 0);
3803 if (TLI.isLittleEndian()) {
3804 for (unsigned i = 0; i != NumBytes; ++i)
3805 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3807 for (unsigned i = 0; i != NumBytes; ++i)
3808 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3811 // If the "cost" of materializing the integer immediate is less than the cost
3812 // of a load, then it is cost effective to turn the load into the immediate.
3813 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3814 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3815 return DAG.getConstant(Val, VT);
3816 return SDValue(nullptr, 0);
3819 /// getMemBasePlusOffset - Returns base and offset node for the
3821 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3822 SelectionDAG &DAG) {
3823 EVT VT = Base.getValueType();
3824 return DAG.getNode(ISD::ADD, dl,
3825 VT, Base, DAG.getConstant(Offset, VT));
3828 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3830 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3831 unsigned SrcDelta = 0;
3832 GlobalAddressSDNode *G = nullptr;
3833 if (Src.getOpcode() == ISD::GlobalAddress)
3834 G = cast<GlobalAddressSDNode>(Src);
3835 else if (Src.getOpcode() == ISD::ADD &&
3836 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3837 Src.getOperand(1).getOpcode() == ISD::Constant) {
3838 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3839 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3844 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3847 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3848 /// to replace the memset / memcpy. Return true if the number of memory ops
3849 /// is below the threshold. It returns the types of the sequence of
3850 /// memory ops to perform memset / memcpy by reference.
3851 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3852 unsigned Limit, uint64_t Size,
3853 unsigned DstAlign, unsigned SrcAlign,
3859 const TargetLowering &TLI) {
3860 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3861 "Expecting memcpy / memset source to meet alignment requirement!");
3862 // If 'SrcAlign' is zero, that means the memory operation does not need to
3863 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3864 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3865 // is the specified alignment of the memory operation. If it is zero, that
3866 // means it's possible to change the alignment of the destination.
3867 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3868 // not need to be loaded.
3869 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3870 IsMemset, ZeroMemset, MemcpyStrSrc,
3871 DAG.getMachineFunction());
3873 if (VT == MVT::Other) {
3875 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3876 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3877 VT = TLI.getPointerTy();
3879 switch (DstAlign & 7) {
3880 case 0: VT = MVT::i64; break;
3881 case 4: VT = MVT::i32; break;
3882 case 2: VT = MVT::i16; break;
3883 default: VT = MVT::i8; break;
3888 while (!TLI.isTypeLegal(LVT))
3889 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3890 assert(LVT.isInteger());
3896 unsigned NumMemOps = 0;
3898 unsigned VTSize = VT.getSizeInBits() / 8;
3899 while (VTSize > Size) {
3900 // For now, only use non-vector load / store's for the left-over pieces.
3905 if (VT.isVector() || VT.isFloatingPoint()) {
3906 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3907 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3908 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3910 else if (NewVT == MVT::i64 &&
3911 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3912 TLI.isSafeMemOpType(MVT::f64)) {
3913 // i64 is usually not legal on 32-bit targets, but f64 may be.
3921 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3922 if (NewVT == MVT::i8)
3924 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3926 NewVTSize = NewVT.getSizeInBits() / 8;
3928 // If the new VT cannot cover all of the remaining bits, then consider
3929 // issuing a (or a pair of) unaligned and overlapping load / store.
3930 // FIXME: Only does this for 64-bit or more since we don't have proper
3931 // cost model for unaligned load / store.
3934 if (NumMemOps && AllowOverlap &&
3935 VTSize >= 8 && NewVTSize < Size &&
3936 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3944 if (++NumMemOps > Limit)
3947 MemOps.push_back(VT);
3954 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3955 SDValue Chain, SDValue Dst,
3956 SDValue Src, uint64_t Size,
3957 unsigned Align, bool isVol,
3959 MachinePointerInfo DstPtrInfo,
3960 MachinePointerInfo SrcPtrInfo) {
3961 // Turn a memcpy of undef to nop.
3962 if (Src.getOpcode() == ISD::UNDEF)
3965 // Expand memcpy to a series of load and store ops if the size operand falls
3966 // below a certain threshold.
3967 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3968 // rather than maybe a humongous number of loads and stores.
3969 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3970 std::vector<EVT> MemOps;
3971 bool DstAlignCanChange = false;
3972 MachineFunction &MF = DAG.getMachineFunction();
3973 MachineFrameInfo *MFI = MF.getFrameInfo();
3975 MF.getFunction()->getAttributes().
3976 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3977 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3978 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3979 DstAlignCanChange = true;
3980 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3981 if (Align > SrcAlign)
3984 bool CopyFromStr = isMemSrcFromString(Src, Str);
3985 bool isZeroStr = CopyFromStr && Str.empty();
3986 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3988 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3989 (DstAlignCanChange ? 0 : Align),
3990 (isZeroStr ? 0 : SrcAlign),
3991 false, false, CopyFromStr, true, DAG, TLI))
3994 if (DstAlignCanChange) {
3995 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3996 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3998 // Don't promote to an alignment that would require dynamic stack
4000 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4001 if (!TRI->needsStackRealignment(MF))
4002 while (NewAlign > Align &&
4003 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4006 if (NewAlign > Align) {
4007 // Give the stack frame object a larger alignment if needed.
4008 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4009 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4014 SmallVector<SDValue, 8> OutChains;
4015 unsigned NumMemOps = MemOps.size();
4016 uint64_t SrcOff = 0, DstOff = 0;
4017 for (unsigned i = 0; i != NumMemOps; ++i) {
4019 unsigned VTSize = VT.getSizeInBits() / 8;
4020 SDValue Value, Store;
4022 if (VTSize > Size) {
4023 // Issuing an unaligned load / store pair that overlaps with the previous
4024 // pair. Adjust the offset accordingly.
4025 assert(i == NumMemOps-1 && i != 0);
4026 SrcOff -= VTSize - Size;
4027 DstOff -= VTSize - Size;
4031 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4032 // It's unlikely a store of a vector immediate can be done in a single
4033 // instruction. It would require a load from a constantpool first.
4034 // We only handle zero vectors here.
4035 // FIXME: Handle other cases where store of vector immediate is done in
4036 // a single instruction.
4037 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4038 if (Value.getNode())
4039 Store = DAG.getStore(Chain, dl, Value,
4040 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4041 DstPtrInfo.getWithOffset(DstOff), isVol,
4045 if (!Store.getNode()) {
4046 // The type might not be legal for the target. This should only happen
4047 // if the type is smaller than a legal type, as on PPC, so the right
4048 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4049 // to Load/Store if NVT==VT.
4050 // FIXME does the case above also need this?
4051 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4052 assert(NVT.bitsGE(VT));
4053 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4054 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4055 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4056 false, MinAlign(SrcAlign, SrcOff));
4057 Store = DAG.getTruncStore(Chain, dl, Value,
4058 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4059 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4062 OutChains.push_back(Store);
4068 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4071 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4072 SDValue Chain, SDValue Dst,
4073 SDValue Src, uint64_t Size,
4074 unsigned Align, bool isVol,
4076 MachinePointerInfo DstPtrInfo,
4077 MachinePointerInfo SrcPtrInfo) {
4078 // Turn a memmove of undef to nop.
4079 if (Src.getOpcode() == ISD::UNDEF)
4082 // Expand memmove to a series of load and store ops if the size operand falls
4083 // below a certain threshold.
4084 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4085 std::vector<EVT> MemOps;
4086 bool DstAlignCanChange = false;
4087 MachineFunction &MF = DAG.getMachineFunction();
4088 MachineFrameInfo *MFI = MF.getFrameInfo();
4089 bool OptSize = MF.getFunction()->getAttributes().
4090 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4091 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4092 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4093 DstAlignCanChange = true;
4094 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4095 if (Align > SrcAlign)
4097 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4099 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4100 (DstAlignCanChange ? 0 : Align), SrcAlign,
4101 false, false, false, false, DAG, TLI))
4104 if (DstAlignCanChange) {
4105 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4106 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4107 if (NewAlign > Align) {
4108 // Give the stack frame object a larger alignment if needed.
4109 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4110 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4115 uint64_t SrcOff = 0, DstOff = 0;
4116 SmallVector<SDValue, 8> LoadValues;
4117 SmallVector<SDValue, 8> LoadChains;
4118 SmallVector<SDValue, 8> OutChains;
4119 unsigned NumMemOps = MemOps.size();
4120 for (unsigned i = 0; i < NumMemOps; i++) {
4122 unsigned VTSize = VT.getSizeInBits() / 8;
4125 Value = DAG.getLoad(VT, dl, Chain,
4126 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4127 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4128 false, false, SrcAlign);
4129 LoadValues.push_back(Value);
4130 LoadChains.push_back(Value.getValue(1));
4133 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4135 for (unsigned i = 0; i < NumMemOps; i++) {
4137 unsigned VTSize = VT.getSizeInBits() / 8;
4140 Store = DAG.getStore(Chain, dl, LoadValues[i],
4141 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4142 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4143 OutChains.push_back(Store);
4147 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4150 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4153 /// \param DAG Selection DAG where lowered code is placed.
4154 /// \param dl Link to corresponding IR location.
4155 /// \param Chain Control flow dependency.
4156 /// \param Dst Pointer to destination memory location.
4157 /// \param Src Value of byte to write into the memory.
4158 /// \param Size Number of bytes to write.
4159 /// \param Align Alignment of the destination in bytes.
4160 /// \param isVol True if destination is volatile.
4161 /// \param DstPtrInfo IR information on the memory pointer.
4162 /// \returns New head in the control flow, if lowering was successful, empty
4163 /// SDValue otherwise.
4165 /// The function tries to replace 'llvm.memset' intrinsic with several store
4166 /// operations and value calculation code. This is usually profitable for small
4168 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4169 SDValue Chain, SDValue Dst,
4170 SDValue Src, uint64_t Size,
4171 unsigned Align, bool isVol,
4172 MachinePointerInfo DstPtrInfo) {
4173 // Turn a memset of undef to nop.
4174 if (Src.getOpcode() == ISD::UNDEF)
4177 // Expand memset to a series of load/store ops if the size operand
4178 // falls below a certain threshold.
4179 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4180 std::vector<EVT> MemOps;
4181 bool DstAlignCanChange = false;
4182 MachineFunction &MF = DAG.getMachineFunction();
4183 MachineFrameInfo *MFI = MF.getFrameInfo();
4184 bool OptSize = MF.getFunction()->getAttributes().
4185 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4186 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4187 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4188 DstAlignCanChange = true;
4190 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4191 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4192 Size, (DstAlignCanChange ? 0 : Align), 0,
4193 true, IsZeroVal, false, true, DAG, TLI))
4196 if (DstAlignCanChange) {
4197 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4198 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4199 if (NewAlign > Align) {
4200 // Give the stack frame object a larger alignment if needed.
4201 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4202 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4207 SmallVector<SDValue, 8> OutChains;
4208 uint64_t DstOff = 0;
4209 unsigned NumMemOps = MemOps.size();
4211 // Find the largest store and generate the bit pattern for it.
4212 EVT LargestVT = MemOps[0];
4213 for (unsigned i = 1; i < NumMemOps; i++)
4214 if (MemOps[i].bitsGT(LargestVT))
4215 LargestVT = MemOps[i];
4216 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4218 for (unsigned i = 0; i < NumMemOps; i++) {
4220 unsigned VTSize = VT.getSizeInBits() / 8;
4221 if (VTSize > Size) {
4222 // Issuing an unaligned load / store pair that overlaps with the previous
4223 // pair. Adjust the offset accordingly.
4224 assert(i == NumMemOps-1 && i != 0);
4225 DstOff -= VTSize - Size;
4228 // If this store is smaller than the largest store see whether we can get
4229 // the smaller value for free with a truncate.
4230 SDValue Value = MemSetValue;
4231 if (VT.bitsLT(LargestVT)) {
4232 if (!LargestVT.isVector() && !VT.isVector() &&
4233 TLI.isTruncateFree(LargestVT, VT))
4234 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4236 Value = getMemsetValue(Src, VT, DAG, dl);
4238 assert(Value.getValueType() == VT && "Value with wrong type.");
4239 SDValue Store = DAG.getStore(Chain, dl, Value,
4240 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4241 DstPtrInfo.getWithOffset(DstOff),
4242 isVol, false, Align);
4243 OutChains.push_back(Store);
4244 DstOff += VT.getSizeInBits() / 8;
4248 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4251 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4252 SDValue Src, SDValue Size,
4253 unsigned Align, bool isVol, bool AlwaysInline,
4254 MachinePointerInfo DstPtrInfo,
4255 MachinePointerInfo SrcPtrInfo) {
4256 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4258 // Check to see if we should lower the memcpy to loads and stores first.
4259 // For cases within the target-specified limits, this is the best choice.
4260 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4262 // Memcpy with size zero? Just return the original chain.
4263 if (ConstantSize->isNullValue())
4266 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4267 ConstantSize->getZExtValue(),Align,
4268 isVol, false, DstPtrInfo, SrcPtrInfo);
4269 if (Result.getNode())
4273 // Then check to see if we should lower the memcpy with target-specific
4274 // code. If the target chooses to do this, this is the next best.
4276 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4277 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4278 DstPtrInfo, SrcPtrInfo);
4279 if (Result.getNode())
4283 // If we really need inline code and the target declined to provide it,
4284 // use a (potentially long) sequence of loads and stores.
4286 assert(ConstantSize && "AlwaysInline requires a constant size!");
4287 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4288 ConstantSize->getZExtValue(), Align, isVol,
4289 true, DstPtrInfo, SrcPtrInfo);
4292 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4293 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4294 // respect volatile, so they may do things like read or write memory
4295 // beyond the given memory regions. But fixing this isn't easy, and most
4296 // people don't care.
4298 // Emit a library call.
4299 TargetLowering::ArgListTy Args;
4300 TargetLowering::ArgListEntry Entry;
4301 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4302 Entry.Node = Dst; Args.push_back(Entry);
4303 Entry.Node = Src; Args.push_back(Entry);
4304 Entry.Node = Size; Args.push_back(Entry);
4305 // FIXME: pass in SDLoc
4306 TargetLowering::CallLoweringInfo CLI(*this);
4307 CLI.setDebugLoc(dl).setChain(Chain)
4308 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4309 Type::getVoidTy(*getContext()),
4310 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4311 TLI->getPointerTy()), std::move(Args), 0)
4312 .setDiscardResult();
4313 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4315 return CallResult.second;
4318 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4319 SDValue Src, SDValue Size,
4320 unsigned Align, bool isVol,
4321 MachinePointerInfo DstPtrInfo,
4322 MachinePointerInfo SrcPtrInfo) {
4323 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4325 // Check to see if we should lower the memmove to loads and stores first.
4326 // For cases within the target-specified limits, this is the best choice.
4327 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4329 // Memmove with size zero? Just return the original chain.
4330 if (ConstantSize->isNullValue())
4334 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4335 ConstantSize->getZExtValue(), Align, isVol,
4336 false, DstPtrInfo, SrcPtrInfo);
4337 if (Result.getNode())
4341 // Then check to see if we should lower the memmove with target-specific
4342 // code. If the target chooses to do this, this is the next best.
4344 SDValue Result = TSI->EmitTargetCodeForMemmove(
4345 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4346 if (Result.getNode())
4350 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4351 // not be safe. See memcpy above for more details.
4353 // Emit a library call.
4354 TargetLowering::ArgListTy Args;
4355 TargetLowering::ArgListEntry Entry;
4356 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4357 Entry.Node = Dst; Args.push_back(Entry);
4358 Entry.Node = Src; Args.push_back(Entry);
4359 Entry.Node = Size; Args.push_back(Entry);
4360 // FIXME: pass in SDLoc
4361 TargetLowering::CallLoweringInfo CLI(*this);
4362 CLI.setDebugLoc(dl).setChain(Chain)
4363 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4364 Type::getVoidTy(*getContext()),
4365 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4366 TLI->getPointerTy()), std::move(Args), 0)
4367 .setDiscardResult();
4368 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4370 return CallResult.second;
4373 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4374 SDValue Src, SDValue Size,
4375 unsigned Align, bool isVol,
4376 MachinePointerInfo DstPtrInfo) {
4377 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4379 // Check to see if we should lower the memset to stores first.
4380 // For cases within the target-specified limits, this is the best choice.
4381 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4383 // Memset with size zero? Just return the original chain.
4384 if (ConstantSize->isNullValue())
4388 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4389 Align, isVol, DstPtrInfo);
4391 if (Result.getNode())
4395 // Then check to see if we should lower the memset with target-specific
4396 // code. If the target chooses to do this, this is the next best.
4398 SDValue Result = TSI->EmitTargetCodeForMemset(
4399 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4400 if (Result.getNode())
4404 // Emit a library call.
4405 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4406 TargetLowering::ArgListTy Args;
4407 TargetLowering::ArgListEntry Entry;
4408 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4409 Args.push_back(Entry);
4411 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4412 Args.push_back(Entry);
4414 Entry.Ty = IntPtrTy;
4415 Args.push_back(Entry);
4417 // FIXME: pass in SDLoc
4418 TargetLowering::CallLoweringInfo CLI(*this);
4419 CLI.setDebugLoc(dl).setChain(Chain)
4420 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4421 Type::getVoidTy(*getContext()),
4422 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4423 TLI->getPointerTy()), std::move(Args), 0)
4424 .setDiscardResult();
4426 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4427 return CallResult.second;
4430 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4431 SDVTList VTList, ArrayRef<SDValue> Ops,
4432 MachineMemOperand *MMO,
4433 AtomicOrdering SuccessOrdering,
4434 AtomicOrdering FailureOrdering,
4435 SynchronizationScope SynchScope) {
4436 FoldingSetNodeID ID;
4437 ID.AddInteger(MemVT.getRawBits());
4438 AddNodeIDNode(ID, Opcode, VTList, Ops);
4439 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4441 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4442 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4443 return SDValue(E, 0);
4446 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4447 // SDNode doesn't have access to it. This memory will be "leaked" when
4448 // the node is deallocated, but recovered when the allocator is released.
4449 // If the number of operands is less than 5 we use AtomicSDNode's internal
4451 unsigned NumOps = Ops.size();
4452 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4455 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4456 dl.getDebugLoc(), VTList, MemVT,
4457 Ops.data(), DynOps, NumOps, MMO,
4458 SuccessOrdering, FailureOrdering,
4460 CSEMap.InsertNode(N, IP);
4462 return SDValue(N, 0);
4465 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4466 SDVTList VTList, ArrayRef<SDValue> Ops,
4467 MachineMemOperand *MMO,
4468 AtomicOrdering Ordering,
4469 SynchronizationScope SynchScope) {
4470 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4471 Ordering, SynchScope);
4474 SDValue SelectionDAG::getAtomicCmpSwap(
4475 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4476 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4477 unsigned Alignment, AtomicOrdering SuccessOrdering,
4478 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4479 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4480 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4481 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4483 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4484 Alignment = getEVTAlignment(MemVT);
4486 MachineFunction &MF = getMachineFunction();
4488 // FIXME: Volatile isn't really correct; we should keep track of atomic
4489 // orderings in the memoperand.
4490 unsigned Flags = MachineMemOperand::MOVolatile;
4491 Flags |= MachineMemOperand::MOLoad;
4492 Flags |= MachineMemOperand::MOStore;
4494 MachineMemOperand *MMO =
4495 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4497 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4498 SuccessOrdering, FailureOrdering, SynchScope);
4501 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4502 SDVTList VTs, SDValue Chain, SDValue Ptr,
4503 SDValue Cmp, SDValue Swp,
4504 MachineMemOperand *MMO,
4505 AtomicOrdering SuccessOrdering,
4506 AtomicOrdering FailureOrdering,
4507 SynchronizationScope SynchScope) {
4508 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4509 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4510 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4512 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4513 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4514 SuccessOrdering, FailureOrdering, SynchScope);
4517 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4519 SDValue Ptr, SDValue Val,
4520 const Value* PtrVal,
4522 AtomicOrdering Ordering,
4523 SynchronizationScope SynchScope) {
4524 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4525 Alignment = getEVTAlignment(MemVT);
4527 MachineFunction &MF = getMachineFunction();
4528 // An atomic store does not load. An atomic load does not store.
4529 // (An atomicrmw obviously both loads and stores.)
4530 // For now, atomics are considered to be volatile always, and they are
4532 // FIXME: Volatile isn't really correct; we should keep track of atomic
4533 // orderings in the memoperand.
4534 unsigned Flags = MachineMemOperand::MOVolatile;
4535 if (Opcode != ISD::ATOMIC_STORE)
4536 Flags |= MachineMemOperand::MOLoad;
4537 if (Opcode != ISD::ATOMIC_LOAD)
4538 Flags |= MachineMemOperand::MOStore;
4540 MachineMemOperand *MMO =
4541 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4542 MemVT.getStoreSize(), Alignment);
4544 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4545 Ordering, SynchScope);
4548 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4550 SDValue Ptr, SDValue Val,
4551 MachineMemOperand *MMO,
4552 AtomicOrdering Ordering,
4553 SynchronizationScope SynchScope) {
4554 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4555 Opcode == ISD::ATOMIC_LOAD_SUB ||
4556 Opcode == ISD::ATOMIC_LOAD_AND ||
4557 Opcode == ISD::ATOMIC_LOAD_OR ||
4558 Opcode == ISD::ATOMIC_LOAD_XOR ||
4559 Opcode == ISD::ATOMIC_LOAD_NAND ||
4560 Opcode == ISD::ATOMIC_LOAD_MIN ||
4561 Opcode == ISD::ATOMIC_LOAD_MAX ||
4562 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4563 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4564 Opcode == ISD::ATOMIC_SWAP ||
4565 Opcode == ISD::ATOMIC_STORE) &&
4566 "Invalid Atomic Op");
4568 EVT VT = Val.getValueType();
4570 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4571 getVTList(VT, MVT::Other);
4572 SDValue Ops[] = {Chain, Ptr, Val};
4573 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4576 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4577 EVT VT, SDValue Chain,
4579 MachineMemOperand *MMO,
4580 AtomicOrdering Ordering,
4581 SynchronizationScope SynchScope) {
4582 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4584 SDVTList VTs = getVTList(VT, MVT::Other);
4585 SDValue Ops[] = {Chain, Ptr};
4586 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4589 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4590 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4591 if (Ops.size() == 1)
4594 SmallVector<EVT, 4> VTs;
4595 VTs.reserve(Ops.size());
4596 for (unsigned i = 0; i < Ops.size(); ++i)
4597 VTs.push_back(Ops[i].getValueType());
4598 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4602 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4603 ArrayRef<SDValue> Ops,
4604 EVT MemVT, MachinePointerInfo PtrInfo,
4605 unsigned Align, bool Vol,
4606 bool ReadMem, bool WriteMem, unsigned Size) {
4607 if (Align == 0) // Ensure that codegen never sees alignment 0
4608 Align = getEVTAlignment(MemVT);
4610 MachineFunction &MF = getMachineFunction();
4613 Flags |= MachineMemOperand::MOStore;
4615 Flags |= MachineMemOperand::MOLoad;
4617 Flags |= MachineMemOperand::MOVolatile;
4619 Size = MemVT.getStoreSize();
4620 MachineMemOperand *MMO =
4621 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4623 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4627 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4628 ArrayRef<SDValue> Ops, EVT MemVT,
4629 MachineMemOperand *MMO) {
4630 assert((Opcode == ISD::INTRINSIC_VOID ||
4631 Opcode == ISD::INTRINSIC_W_CHAIN ||
4632 Opcode == ISD::PREFETCH ||
4633 Opcode == ISD::LIFETIME_START ||
4634 Opcode == ISD::LIFETIME_END ||
4635 (Opcode <= INT_MAX &&
4636 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4637 "Opcode is not a memory-accessing opcode!");
4639 // Memoize the node unless it returns a flag.
4640 MemIntrinsicSDNode *N;
4641 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4642 FoldingSetNodeID ID;
4643 AddNodeIDNode(ID, Opcode, VTList, Ops);
4644 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4646 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4647 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4648 return SDValue(E, 0);
4651 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4652 dl.getDebugLoc(), VTList, Ops,
4654 CSEMap.InsertNode(N, IP);
4656 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4657 dl.getDebugLoc(), VTList, Ops,
4661 return SDValue(N, 0);
4664 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4665 /// MachinePointerInfo record from it. This is particularly useful because the
4666 /// code generator has many cases where it doesn't bother passing in a
4667 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4668 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4669 // If this is FI+Offset, we can model it.
4670 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4671 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4673 // If this is (FI+Offset1)+Offset2, we can model it.
4674 if (Ptr.getOpcode() != ISD::ADD ||
4675 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4676 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4677 return MachinePointerInfo();
4679 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4680 return MachinePointerInfo::getFixedStack(FI, Offset+
4681 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4684 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4685 /// MachinePointerInfo record from it. This is particularly useful because the
4686 /// code generator has many cases where it doesn't bother passing in a
4687 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4688 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4689 // If the 'Offset' value isn't a constant, we can't handle this.
4690 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4691 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4692 if (OffsetOp.getOpcode() == ISD::UNDEF)
4693 return InferPointerInfo(Ptr);
4694 return MachinePointerInfo();
4699 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4700 EVT VT, SDLoc dl, SDValue Chain,
4701 SDValue Ptr, SDValue Offset,
4702 MachinePointerInfo PtrInfo, EVT MemVT,
4703 bool isVolatile, bool isNonTemporal, bool isInvariant,
4704 unsigned Alignment, const AAMDNodes &AAInfo,
4705 const MDNode *Ranges) {
4706 assert(Chain.getValueType() == MVT::Other &&
4707 "Invalid chain type");
4708 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4709 Alignment = getEVTAlignment(VT);
4711 unsigned Flags = MachineMemOperand::MOLoad;
4713 Flags |= MachineMemOperand::MOVolatile;
4715 Flags |= MachineMemOperand::MONonTemporal;
4717 Flags |= MachineMemOperand::MOInvariant;
4719 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4721 if (PtrInfo.V.isNull())
4722 PtrInfo = InferPointerInfo(Ptr, Offset);
4724 MachineFunction &MF = getMachineFunction();
4725 MachineMemOperand *MMO =
4726 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4728 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4732 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4733 EVT VT, SDLoc dl, SDValue Chain,
4734 SDValue Ptr, SDValue Offset, EVT MemVT,
4735 MachineMemOperand *MMO) {
4737 ExtType = ISD::NON_EXTLOAD;
4738 } else if (ExtType == ISD::NON_EXTLOAD) {
4739 assert(VT == MemVT && "Non-extending load from different memory type!");
4742 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4743 "Should only be an extending load, not truncating!");
4744 assert(VT.isInteger() == MemVT.isInteger() &&
4745 "Cannot convert from FP to Int or Int -> FP!");
4746 assert(VT.isVector() == MemVT.isVector() &&
4747 "Cannot use an ext load to convert to or from a vector!");
4748 assert((!VT.isVector() ||
4749 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4750 "Cannot use an ext load to change the number of vector elements!");
4753 bool Indexed = AM != ISD::UNINDEXED;
4754 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4755 "Unindexed load with an offset!");
4757 SDVTList VTs = Indexed ?
4758 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4759 SDValue Ops[] = { Chain, Ptr, Offset };
4760 FoldingSetNodeID ID;
4761 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4762 ID.AddInteger(MemVT.getRawBits());
4763 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4764 MMO->isNonTemporal(),
4765 MMO->isInvariant()));
4766 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4768 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4769 cast<LoadSDNode>(E)->refineAlignment(MMO);
4770 return SDValue(E, 0);
4772 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4773 dl.getDebugLoc(), VTs, AM, ExtType,
4775 CSEMap.InsertNode(N, IP);
4777 return SDValue(N, 0);
4780 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4781 SDValue Chain, SDValue Ptr,
4782 MachinePointerInfo PtrInfo,
4783 bool isVolatile, bool isNonTemporal,
4784 bool isInvariant, unsigned Alignment,
4785 const AAMDNodes &AAInfo,
4786 const MDNode *Ranges) {
4787 SDValue Undef = getUNDEF(Ptr.getValueType());
4788 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4789 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4793 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4794 SDValue Chain, SDValue Ptr,
4795 MachineMemOperand *MMO) {
4796 SDValue Undef = getUNDEF(Ptr.getValueType());
4797 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4801 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4802 SDValue Chain, SDValue Ptr,
4803 MachinePointerInfo PtrInfo, EVT MemVT,
4804 bool isVolatile, bool isNonTemporal,
4805 bool isInvariant, unsigned Alignment,
4806 const AAMDNodes &AAInfo) {
4807 SDValue Undef = getUNDEF(Ptr.getValueType());
4808 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4809 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4814 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4815 SDValue Chain, SDValue Ptr, EVT MemVT,
4816 MachineMemOperand *MMO) {
4817 SDValue Undef = getUNDEF(Ptr.getValueType());
4818 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4823 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4824 SDValue Offset, ISD::MemIndexedMode AM) {
4825 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4826 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4827 "Load is already a indexed load!");
4828 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4829 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4830 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4831 false, LD->getAlignment());
4834 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4835 SDValue Ptr, MachinePointerInfo PtrInfo,
4836 bool isVolatile, bool isNonTemporal,
4837 unsigned Alignment, const AAMDNodes &AAInfo) {
4838 assert(Chain.getValueType() == MVT::Other &&
4839 "Invalid chain type");
4840 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4841 Alignment = getEVTAlignment(Val.getValueType());
4843 unsigned Flags = MachineMemOperand::MOStore;
4845 Flags |= MachineMemOperand::MOVolatile;
4847 Flags |= MachineMemOperand::MONonTemporal;
4849 if (PtrInfo.V.isNull())
4850 PtrInfo = InferPointerInfo(Ptr);
4852 MachineFunction &MF = getMachineFunction();
4853 MachineMemOperand *MMO =
4854 MF.getMachineMemOperand(PtrInfo, Flags,
4855 Val.getValueType().getStoreSize(), Alignment,
4858 return getStore(Chain, dl, Val, Ptr, MMO);
4861 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4862 SDValue Ptr, MachineMemOperand *MMO) {
4863 assert(Chain.getValueType() == MVT::Other &&
4864 "Invalid chain type");
4865 EVT VT = Val.getValueType();
4866 SDVTList VTs = getVTList(MVT::Other);
4867 SDValue Undef = getUNDEF(Ptr.getValueType());
4868 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4869 FoldingSetNodeID ID;
4870 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4871 ID.AddInteger(VT.getRawBits());
4872 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4873 MMO->isNonTemporal(), MMO->isInvariant()));
4874 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4876 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4877 cast<StoreSDNode>(E)->refineAlignment(MMO);
4878 return SDValue(E, 0);
4880 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4881 dl.getDebugLoc(), VTs,
4882 ISD::UNINDEXED, false, VT, MMO);
4883 CSEMap.InsertNode(N, IP);
4885 return SDValue(N, 0);
4888 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4889 SDValue Ptr, MachinePointerInfo PtrInfo,
4890 EVT SVT,bool isVolatile, bool isNonTemporal,
4892 const AAMDNodes &AAInfo) {
4893 assert(Chain.getValueType() == MVT::Other &&
4894 "Invalid chain type");
4895 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4896 Alignment = getEVTAlignment(SVT);
4898 unsigned Flags = MachineMemOperand::MOStore;
4900 Flags |= MachineMemOperand::MOVolatile;
4902 Flags |= MachineMemOperand::MONonTemporal;
4904 if (PtrInfo.V.isNull())
4905 PtrInfo = InferPointerInfo(Ptr);
4907 MachineFunction &MF = getMachineFunction();
4908 MachineMemOperand *MMO =
4909 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4912 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4915 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4916 SDValue Ptr, EVT SVT,
4917 MachineMemOperand *MMO) {
4918 EVT VT = Val.getValueType();
4920 assert(Chain.getValueType() == MVT::Other &&
4921 "Invalid chain type");
4923 return getStore(Chain, dl, Val, Ptr, MMO);
4925 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4926 "Should only be a truncating store, not extending!");
4927 assert(VT.isInteger() == SVT.isInteger() &&
4928 "Can't do FP-INT conversion!");
4929 assert(VT.isVector() == SVT.isVector() &&
4930 "Cannot use trunc store to convert to or from a vector!");
4931 assert((!VT.isVector() ||
4932 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4933 "Cannot use trunc store to change the number of vector elements!");
4935 SDVTList VTs = getVTList(MVT::Other);
4936 SDValue Undef = getUNDEF(Ptr.getValueType());
4937 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4938 FoldingSetNodeID ID;
4939 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4940 ID.AddInteger(SVT.getRawBits());
4941 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4942 MMO->isNonTemporal(), MMO->isInvariant()));
4943 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4945 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4946 cast<StoreSDNode>(E)->refineAlignment(MMO);
4947 return SDValue(E, 0);
4949 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4950 dl.getDebugLoc(), VTs,
4951 ISD::UNINDEXED, true, SVT, MMO);
4952 CSEMap.InsertNode(N, IP);
4954 return SDValue(N, 0);
4958 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4959 SDValue Offset, ISD::MemIndexedMode AM) {
4960 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4961 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4962 "Store is already a indexed store!");
4963 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4964 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4965 FoldingSetNodeID ID;
4966 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4967 ID.AddInteger(ST->getMemoryVT().getRawBits());
4968 ID.AddInteger(ST->getRawSubclassData());
4969 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4971 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4972 return SDValue(E, 0);
4974 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4975 dl.getDebugLoc(), VTs, AM,
4976 ST->isTruncatingStore(),
4978 ST->getMemOperand());
4979 CSEMap.InsertNode(N, IP);
4981 return SDValue(N, 0);
4985 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
4986 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
4987 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
4989 SDVTList VTs = getVTList(VT, MVT::Other);
4990 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
4991 FoldingSetNodeID ID;
4992 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
4993 ID.AddInteger(VT.getRawBits());
4994 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
4996 MMO->isNonTemporal(),
4997 MMO->isInvariant()));
4998 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5000 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5001 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5002 return SDValue(E, 0);
5004 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5005 dl.getDebugLoc(), Ops, 4, VTs,
5007 CSEMap.InsertNode(N, IP);
5009 return SDValue(N, 0);
5012 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5013 SDValue Ptr, SDValue Mask, EVT MemVT,
5014 MachineMemOperand *MMO, bool isTrunc) {
5015 assert(Chain.getValueType() == MVT::Other &&
5016 "Invalid chain type");
5017 EVT VT = Val.getValueType();
5018 SDVTList VTs = getVTList(MVT::Other);
5019 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5020 FoldingSetNodeID ID;
5021 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5022 ID.AddInteger(VT.getRawBits());
5023 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5024 MMO->isNonTemporal(), MMO->isInvariant()));
5025 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5027 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5028 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5029 return SDValue(E, 0);
5031 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5032 dl.getDebugLoc(), Ops, 4,
5033 VTs, isTrunc, MemVT, MMO);
5034 CSEMap.InsertNode(N, IP);
5036 return SDValue(N, 0);
5039 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5040 SDValue Chain, SDValue Ptr,
5043 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5044 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5047 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5048 ArrayRef<SDUse> Ops) {
5049 switch (Ops.size()) {
5050 case 0: return getNode(Opcode, DL, VT);
5051 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5052 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5053 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5057 // Copy from an SDUse array into an SDValue array for use with
5058 // the regular getNode logic.
5059 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5060 return getNode(Opcode, DL, VT, NewOps);
5063 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5064 ArrayRef<SDValue> Ops) {
5065 unsigned NumOps = Ops.size();
5067 case 0: return getNode(Opcode, DL, VT);
5068 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5069 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5070 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5076 case ISD::SELECT_CC: {
5077 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5078 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5079 "LHS and RHS of condition must have same type!");
5080 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5081 "True and False arms of SelectCC must have same type!");
5082 assert(Ops[2].getValueType() == VT &&
5083 "select_cc node must be of same type as true and false value!");
5087 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5088 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5089 "LHS/RHS of comparison should match types!");
5096 SDVTList VTs = getVTList(VT);
5098 if (VT != MVT::Glue) {
5099 FoldingSetNodeID ID;
5100 AddNodeIDNode(ID, Opcode, VTs, Ops);
5103 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5104 return SDValue(E, 0);
5106 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5108 CSEMap.InsertNode(N, IP);
5110 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5115 return SDValue(N, 0);
5118 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5119 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5120 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5123 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5124 ArrayRef<SDValue> Ops) {
5125 if (VTList.NumVTs == 1)
5126 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5130 // FIXME: figure out how to safely handle things like
5131 // int foo(int x) { return 1 << (x & 255); }
5132 // int bar() { return foo(256); }
5133 case ISD::SRA_PARTS:
5134 case ISD::SRL_PARTS:
5135 case ISD::SHL_PARTS:
5136 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5137 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5138 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5139 else if (N3.getOpcode() == ISD::AND)
5140 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5141 // If the and is only masking out bits that cannot effect the shift,
5142 // eliminate the and.
5143 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5144 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5145 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5151 // Memoize the node unless it returns a flag.
5153 unsigned NumOps = Ops.size();
5154 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5155 FoldingSetNodeID ID;
5156 AddNodeIDNode(ID, Opcode, VTList, Ops);
5158 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5159 return SDValue(E, 0);
5162 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5163 DL.getDebugLoc(), VTList, Ops[0]);
5164 } else if (NumOps == 2) {
5165 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5166 DL.getDebugLoc(), VTList, Ops[0],
5168 } else if (NumOps == 3) {
5169 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5170 DL.getDebugLoc(), VTList, Ops[0],
5173 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5176 CSEMap.InsertNode(N, IP);
5179 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5180 DL.getDebugLoc(), VTList, Ops[0]);
5181 } else if (NumOps == 2) {
5182 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5183 DL.getDebugLoc(), VTList, Ops[0],
5185 } else if (NumOps == 3) {
5186 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5187 DL.getDebugLoc(), VTList, Ops[0],
5190 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5195 return SDValue(N, 0);
5198 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5199 return getNode(Opcode, DL, VTList, None);
5202 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5204 SDValue Ops[] = { N1 };
5205 return getNode(Opcode, DL, VTList, Ops);
5208 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5209 SDValue N1, SDValue N2) {
5210 SDValue Ops[] = { N1, N2 };
5211 return getNode(Opcode, DL, VTList, Ops);
5214 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5215 SDValue N1, SDValue N2, SDValue N3) {
5216 SDValue Ops[] = { N1, N2, N3 };
5217 return getNode(Opcode, DL, VTList, Ops);
5220 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5221 SDValue N1, SDValue N2, SDValue N3,
5223 SDValue Ops[] = { N1, N2, N3, N4 };
5224 return getNode(Opcode, DL, VTList, Ops);
5227 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5228 SDValue N1, SDValue N2, SDValue N3,
5229 SDValue N4, SDValue N5) {
5230 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5231 return getNode(Opcode, DL, VTList, Ops);
5234 SDVTList SelectionDAG::getVTList(EVT VT) {
5235 return makeVTList(SDNode::getValueTypeList(VT), 1);
5238 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5239 FoldingSetNodeID ID;
5241 ID.AddInteger(VT1.getRawBits());
5242 ID.AddInteger(VT2.getRawBits());
5245 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5247 EVT *Array = Allocator.Allocate<EVT>(2);
5250 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5251 VTListMap.InsertNode(Result, IP);
5253 return Result->getSDVTList();
5256 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5257 FoldingSetNodeID ID;
5259 ID.AddInteger(VT1.getRawBits());
5260 ID.AddInteger(VT2.getRawBits());
5261 ID.AddInteger(VT3.getRawBits());
5264 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5266 EVT *Array = Allocator.Allocate<EVT>(3);
5270 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5271 VTListMap.InsertNode(Result, IP);
5273 return Result->getSDVTList();
5276 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5277 FoldingSetNodeID ID;
5279 ID.AddInteger(VT1.getRawBits());
5280 ID.AddInteger(VT2.getRawBits());
5281 ID.AddInteger(VT3.getRawBits());
5282 ID.AddInteger(VT4.getRawBits());
5285 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5287 EVT *Array = Allocator.Allocate<EVT>(4);
5292 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5293 VTListMap.InsertNode(Result, IP);
5295 return Result->getSDVTList();
5298 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5299 unsigned NumVTs = VTs.size();
5300 FoldingSetNodeID ID;
5301 ID.AddInteger(NumVTs);
5302 for (unsigned index = 0; index < NumVTs; index++) {
5303 ID.AddInteger(VTs[index].getRawBits());
5307 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5309 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5310 std::copy(VTs.begin(), VTs.end(), Array);
5311 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5312 VTListMap.InsertNode(Result, IP);
5314 return Result->getSDVTList();
5318 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5319 /// specified operands. If the resultant node already exists in the DAG,
5320 /// this does not modify the specified node, instead it returns the node that
5321 /// already exists. If the resultant node does not exist in the DAG, the
5322 /// input node is returned. As a degenerate case, if you specify the same
5323 /// input operands as the node already has, the input node is returned.
5324 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5325 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5327 // Check to see if there is no change.
5328 if (Op == N->getOperand(0)) return N;
5330 // See if the modified node already exists.
5331 void *InsertPos = nullptr;
5332 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5335 // Nope it doesn't. Remove the node from its current place in the maps.
5337 if (!RemoveNodeFromCSEMaps(N))
5338 InsertPos = nullptr;
5340 // Now we update the operands.
5341 N->OperandList[0].set(Op);
5343 // If this gets put into a CSE map, add it.
5344 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5348 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5349 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5351 // Check to see if there is no change.
5352 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5353 return N; // No operands changed, just return the input node.
5355 // See if the modified node already exists.
5356 void *InsertPos = nullptr;
5357 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5360 // Nope it doesn't. Remove the node from its current place in the maps.
5362 if (!RemoveNodeFromCSEMaps(N))
5363 InsertPos = nullptr;
5365 // Now we update the operands.
5366 if (N->OperandList[0] != Op1)
5367 N->OperandList[0].set(Op1);
5368 if (N->OperandList[1] != Op2)
5369 N->OperandList[1].set(Op2);
5371 // If this gets put into a CSE map, add it.
5372 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5376 SDNode *SelectionDAG::
5377 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5378 SDValue Ops[] = { Op1, Op2, Op3 };
5379 return UpdateNodeOperands(N, Ops);
5382 SDNode *SelectionDAG::
5383 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5384 SDValue Op3, SDValue Op4) {
5385 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5386 return UpdateNodeOperands(N, Ops);
5389 SDNode *SelectionDAG::
5390 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5391 SDValue Op3, SDValue Op4, SDValue Op5) {
5392 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5393 return UpdateNodeOperands(N, Ops);
5396 SDNode *SelectionDAG::
5397 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5398 unsigned NumOps = Ops.size();
5399 assert(N->getNumOperands() == NumOps &&
5400 "Update with wrong number of operands");
5402 // Check to see if there is no change.
5403 bool AnyChange = false;
5404 for (unsigned i = 0; i != NumOps; ++i) {
5405 if (Ops[i] != N->getOperand(i)) {
5411 // No operands changed, just return the input node.
5412 if (!AnyChange) return N;
5414 // See if the modified node already exists.
5415 void *InsertPos = nullptr;
5416 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5419 // Nope it doesn't. Remove the node from its current place in the maps.
5421 if (!RemoveNodeFromCSEMaps(N))
5422 InsertPos = nullptr;
5424 // Now we update the operands.
5425 for (unsigned i = 0; i != NumOps; ++i)
5426 if (N->OperandList[i] != Ops[i])
5427 N->OperandList[i].set(Ops[i]);
5429 // If this gets put into a CSE map, add it.
5430 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5434 /// DropOperands - Release the operands and set this node to have
5436 void SDNode::DropOperands() {
5437 // Unlike the code in MorphNodeTo that does this, we don't need to
5438 // watch for dead nodes here.
5439 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5445 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5448 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5450 SDVTList VTs = getVTList(VT);
5451 return SelectNodeTo(N, MachineOpc, VTs, None);
5454 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5455 EVT VT, SDValue Op1) {
5456 SDVTList VTs = getVTList(VT);
5457 SDValue Ops[] = { Op1 };
5458 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5461 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5462 EVT VT, SDValue Op1,
5464 SDVTList VTs = getVTList(VT);
5465 SDValue Ops[] = { Op1, Op2 };
5466 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5469 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5470 EVT VT, SDValue Op1,
5471 SDValue Op2, SDValue Op3) {
5472 SDVTList VTs = getVTList(VT);
5473 SDValue Ops[] = { Op1, Op2, Op3 };
5474 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5477 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5478 EVT VT, ArrayRef<SDValue> Ops) {
5479 SDVTList VTs = getVTList(VT);
5480 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5483 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5484 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5485 SDVTList VTs = getVTList(VT1, VT2);
5486 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5489 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5491 SDVTList VTs = getVTList(VT1, VT2);
5492 return SelectNodeTo(N, MachineOpc, VTs, None);
5495 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5496 EVT VT1, EVT VT2, EVT VT3,
5497 ArrayRef<SDValue> Ops) {
5498 SDVTList VTs = getVTList(VT1, VT2, VT3);
5499 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5502 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5503 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5504 ArrayRef<SDValue> Ops) {
5505 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5506 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5509 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5512 SDVTList VTs = getVTList(VT1, VT2);
5513 SDValue Ops[] = { Op1 };
5514 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5517 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5519 SDValue Op1, SDValue Op2) {
5520 SDVTList VTs = getVTList(VT1, VT2);
5521 SDValue Ops[] = { Op1, Op2 };
5522 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5525 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5527 SDValue Op1, SDValue Op2,
5529 SDVTList VTs = getVTList(VT1, VT2);
5530 SDValue Ops[] = { Op1, Op2, Op3 };
5531 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5534 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5535 EVT VT1, EVT VT2, EVT VT3,
5536 SDValue Op1, SDValue Op2,
5538 SDVTList VTs = getVTList(VT1, VT2, VT3);
5539 SDValue Ops[] = { Op1, Op2, Op3 };
5540 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5543 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5544 SDVTList VTs,ArrayRef<SDValue> Ops) {
5545 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5546 // Reset the NodeID to -1.
5551 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5552 /// the line number information on the merged node since it is not possible to
5553 /// preserve the information that operation is associated with multiple lines.
5554 /// This will make the debugger working better at -O0, were there is a higher
5555 /// probability having other instructions associated with that line.
5557 /// For IROrder, we keep the smaller of the two
5558 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5559 DebugLoc NLoc = N->getDebugLoc();
5560 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5561 (OLoc.getDebugLoc() != NLoc)) {
5562 N->setDebugLoc(DebugLoc());
5564 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5565 N->setIROrder(Order);
5569 /// MorphNodeTo - This *mutates* the specified node to have the specified
5570 /// return type, opcode, and operands.
5572 /// Note that MorphNodeTo returns the resultant node. If there is already a
5573 /// node of the specified opcode and operands, it returns that node instead of
5574 /// the current one. Note that the SDLoc need not be the same.
5576 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5577 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5578 /// node, and because it doesn't require CSE recalculation for any of
5579 /// the node's users.
5581 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5582 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5583 /// the legalizer which maintain worklists that would need to be updated when
5584 /// deleting things.
5585 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5586 SDVTList VTs, ArrayRef<SDValue> Ops) {
5587 unsigned NumOps = Ops.size();
5588 // If an identical node already exists, use it.
5590 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5591 FoldingSetNodeID ID;
5592 AddNodeIDNode(ID, Opc, VTs, Ops);
5593 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5594 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5597 if (!RemoveNodeFromCSEMaps(N))
5600 // Start the morphing.
5602 N->ValueList = VTs.VTs;
5603 N->NumValues = VTs.NumVTs;
5605 // Clear the operands list, updating used nodes to remove this from their
5606 // use list. Keep track of any operands that become dead as a result.
5607 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5608 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5610 SDNode *Used = Use.getNode();
5612 if (Used->use_empty())
5613 DeadNodeSet.insert(Used);
5616 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5617 // Initialize the memory references information.
5618 MN->setMemRefs(nullptr, nullptr);
5619 // If NumOps is larger than the # of operands we can have in a
5620 // MachineSDNode, reallocate the operand list.
5621 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5622 if (MN->OperandsNeedDelete)
5623 delete[] MN->OperandList;
5624 if (NumOps > array_lengthof(MN->LocalOperands))
5625 // We're creating a final node that will live unmorphed for the
5626 // remainder of the current SelectionDAG iteration, so we can allocate
5627 // the operands directly out of a pool with no recycling metadata.
5628 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5629 Ops.data(), NumOps);
5631 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5632 MN->OperandsNeedDelete = false;
5634 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5636 // If NumOps is larger than the # of operands we currently have, reallocate
5637 // the operand list.
5638 if (NumOps > N->NumOperands) {
5639 if (N->OperandsNeedDelete)
5640 delete[] N->OperandList;
5641 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5642 N->OperandsNeedDelete = true;
5644 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5647 // Delete any nodes that are still dead after adding the uses for the
5649 if (!DeadNodeSet.empty()) {
5650 SmallVector<SDNode *, 16> DeadNodes;
5651 for (SDNode *N : DeadNodeSet)
5653 DeadNodes.push_back(N);
5654 RemoveDeadNodes(DeadNodes);
5658 CSEMap.InsertNode(N, IP); // Memoize the new node.
5663 /// getMachineNode - These are used for target selectors to create a new node
5664 /// with specified return type(s), MachineInstr opcode, and operands.
5666 /// Note that getMachineNode returns the resultant node. If there is already a
5667 /// node of the specified opcode and operands, it returns that node instead of
5668 /// the current one.
5670 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5671 SDVTList VTs = getVTList(VT);
5672 return getMachineNode(Opcode, dl, VTs, None);
5676 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5677 SDVTList VTs = getVTList(VT);
5678 SDValue Ops[] = { Op1 };
5679 return getMachineNode(Opcode, dl, VTs, Ops);
5683 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5684 SDValue Op1, SDValue Op2) {
5685 SDVTList VTs = getVTList(VT);
5686 SDValue Ops[] = { Op1, Op2 };
5687 return getMachineNode(Opcode, dl, VTs, Ops);
5691 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5692 SDValue Op1, SDValue Op2, SDValue Op3) {
5693 SDVTList VTs = getVTList(VT);
5694 SDValue Ops[] = { Op1, Op2, Op3 };
5695 return getMachineNode(Opcode, dl, VTs, Ops);
5699 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5700 ArrayRef<SDValue> Ops) {
5701 SDVTList VTs = getVTList(VT);
5702 return getMachineNode(Opcode, dl, VTs, Ops);
5706 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5707 SDVTList VTs = getVTList(VT1, VT2);
5708 return getMachineNode(Opcode, dl, VTs, None);
5712 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5713 EVT VT1, EVT VT2, SDValue Op1) {
5714 SDVTList VTs = getVTList(VT1, VT2);
5715 SDValue Ops[] = { Op1 };
5716 return getMachineNode(Opcode, dl, VTs, Ops);
5720 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5721 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5722 SDVTList VTs = getVTList(VT1, VT2);
5723 SDValue Ops[] = { Op1, Op2 };
5724 return getMachineNode(Opcode, dl, VTs, Ops);
5728 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5729 EVT VT1, EVT VT2, SDValue Op1,
5730 SDValue Op2, SDValue Op3) {
5731 SDVTList VTs = getVTList(VT1, VT2);
5732 SDValue Ops[] = { Op1, Op2, Op3 };
5733 return getMachineNode(Opcode, dl, VTs, Ops);
5737 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5739 ArrayRef<SDValue> Ops) {
5740 SDVTList VTs = getVTList(VT1, VT2);
5741 return getMachineNode(Opcode, dl, VTs, Ops);
5745 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5746 EVT VT1, EVT VT2, EVT VT3,
5747 SDValue Op1, SDValue Op2) {
5748 SDVTList VTs = getVTList(VT1, VT2, VT3);
5749 SDValue Ops[] = { Op1, Op2 };
5750 return getMachineNode(Opcode, dl, VTs, Ops);
5754 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5755 EVT VT1, EVT VT2, EVT VT3,
5756 SDValue Op1, SDValue Op2, SDValue Op3) {
5757 SDVTList VTs = getVTList(VT1, VT2, VT3);
5758 SDValue Ops[] = { Op1, Op2, Op3 };
5759 return getMachineNode(Opcode, dl, VTs, Ops);
5763 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5764 EVT VT1, EVT VT2, EVT VT3,
5765 ArrayRef<SDValue> Ops) {
5766 SDVTList VTs = getVTList(VT1, VT2, VT3);
5767 return getMachineNode(Opcode, dl, VTs, Ops);
5771 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5772 EVT VT2, EVT VT3, EVT VT4,
5773 ArrayRef<SDValue> Ops) {
5774 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5775 return getMachineNode(Opcode, dl, VTs, Ops);
5779 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5780 ArrayRef<EVT> ResultTys,
5781 ArrayRef<SDValue> Ops) {
5782 SDVTList VTs = getVTList(ResultTys);
5783 return getMachineNode(Opcode, dl, VTs, Ops);
5787 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5788 ArrayRef<SDValue> OpsArray) {
5789 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5792 const SDValue *Ops = OpsArray.data();
5793 unsigned NumOps = OpsArray.size();
5796 FoldingSetNodeID ID;
5797 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5799 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5800 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5804 // Allocate a new MachineSDNode.
5805 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5806 DL.getDebugLoc(), VTs);
5808 // Initialize the operands list.
5809 if (NumOps > array_lengthof(N->LocalOperands))
5810 // We're creating a final node that will live unmorphed for the
5811 // remainder of the current SelectionDAG iteration, so we can allocate
5812 // the operands directly out of a pool with no recycling metadata.
5813 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5816 N->InitOperands(N->LocalOperands, Ops, NumOps);
5817 N->OperandsNeedDelete = false;
5820 CSEMap.InsertNode(N, IP);
5826 /// getTargetExtractSubreg - A convenience function for creating
5827 /// TargetOpcode::EXTRACT_SUBREG nodes.
5829 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5831 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5832 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5833 VT, Operand, SRIdxVal);
5834 return SDValue(Subreg, 0);
5837 /// getTargetInsertSubreg - A convenience function for creating
5838 /// TargetOpcode::INSERT_SUBREG nodes.
5840 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5841 SDValue Operand, SDValue Subreg) {
5842 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5843 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5844 VT, Operand, Subreg, SRIdxVal);
5845 return SDValue(Result, 0);
5848 /// getNodeIfExists - Get the specified node if it's already available, or
5849 /// else return NULL.
5850 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5851 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5853 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5854 FoldingSetNodeID ID;
5855 AddNodeIDNode(ID, Opcode, VTList, Ops);
5856 if (isBinOpWithFlags(Opcode))
5857 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5859 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5865 /// getDbgValue - Creates a SDDbgValue node.
5868 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5869 unsigned R, bool IsIndirect, uint64_t Off,
5870 DebugLoc DL, unsigned O) {
5871 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5875 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5876 const Value *C, uint64_t Off,
5877 DebugLoc DL, unsigned O) {
5878 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5882 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5883 unsigned FI, uint64_t Off,
5884 DebugLoc DL, unsigned O) {
5885 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5890 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5891 /// pointed to by a use iterator is deleted, increment the use iterator
5892 /// so that it doesn't dangle.
5894 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5895 SDNode::use_iterator &UI;
5896 SDNode::use_iterator &UE;
5898 void NodeDeleted(SDNode *N, SDNode *E) override {
5899 // Increment the iterator as needed.
5900 while (UI != UE && N == *UI)
5905 RAUWUpdateListener(SelectionDAG &d,
5906 SDNode::use_iterator &ui,
5907 SDNode::use_iterator &ue)
5908 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5913 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5914 /// This can cause recursive merging of nodes in the DAG.
5916 /// This version assumes From has a single result value.
5918 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5919 SDNode *From = FromN.getNode();
5920 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5921 "Cannot replace with this method!");
5922 assert(From != To.getNode() && "Cannot replace uses of with self");
5924 // Iterate over all the existing uses of From. New uses will be added
5925 // to the beginning of the use list, which we avoid visiting.
5926 // This specifically avoids visiting uses of From that arise while the
5927 // replacement is happening, because any such uses would be the result
5928 // of CSE: If an existing node looks like From after one of its operands
5929 // is replaced by To, we don't want to replace of all its users with To
5930 // too. See PR3018 for more info.
5931 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5932 RAUWUpdateListener Listener(*this, UI, UE);
5936 // This node is about to morph, remove its old self from the CSE maps.
5937 RemoveNodeFromCSEMaps(User);
5939 // A user can appear in a use list multiple times, and when this
5940 // happens the uses are usually next to each other in the list.
5941 // To help reduce the number of CSE recomputations, process all
5942 // the uses of this user that we can find this way.
5944 SDUse &Use = UI.getUse();
5947 } while (UI != UE && *UI == User);
5949 // Now that we have modified User, add it back to the CSE maps. If it
5950 // already exists there, recursively merge the results together.
5951 AddModifiedNodeToCSEMaps(User);
5954 // If we just RAUW'd the root, take note.
5955 if (FromN == getRoot())
5959 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5960 /// This can cause recursive merging of nodes in the DAG.
5962 /// This version assumes that for each value of From, there is a
5963 /// corresponding value in To in the same position with the same type.
5965 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5967 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5968 assert((!From->hasAnyUseOfValue(i) ||
5969 From->getValueType(i) == To->getValueType(i)) &&
5970 "Cannot use this version of ReplaceAllUsesWith!");
5973 // Handle the trivial case.
5977 // Iterate over just the existing users of From. See the comments in
5978 // the ReplaceAllUsesWith above.
5979 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5980 RAUWUpdateListener Listener(*this, UI, UE);
5984 // This node is about to morph, remove its old self from the CSE maps.
5985 RemoveNodeFromCSEMaps(User);
5987 // A user can appear in a use list multiple times, and when this
5988 // happens the uses are usually next to each other in the list.
5989 // To help reduce the number of CSE recomputations, process all
5990 // the uses of this user that we can find this way.
5992 SDUse &Use = UI.getUse();
5995 } while (UI != UE && *UI == User);
5997 // Now that we have modified User, add it back to the CSE maps. If it
5998 // already exists there, recursively merge the results together.
5999 AddModifiedNodeToCSEMaps(User);
6002 // If we just RAUW'd the root, take note.
6003 if (From == getRoot().getNode())
6004 setRoot(SDValue(To, getRoot().getResNo()));
6007 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6008 /// This can cause recursive merging of nodes in the DAG.
6010 /// This version can replace From with any result values. To must match the
6011 /// number and types of values returned by From.
6012 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6013 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6014 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6016 // Iterate over just the existing users of From. See the comments in
6017 // the ReplaceAllUsesWith above.
6018 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6019 RAUWUpdateListener Listener(*this, UI, UE);
6023 // This node is about to morph, remove its old self from the CSE maps.
6024 RemoveNodeFromCSEMaps(User);
6026 // A user can appear in a use list multiple times, and when this
6027 // happens the uses are usually next to each other in the list.
6028 // To help reduce the number of CSE recomputations, process all
6029 // the uses of this user that we can find this way.
6031 SDUse &Use = UI.getUse();
6032 const SDValue &ToOp = To[Use.getResNo()];
6035 } while (UI != UE && *UI == User);
6037 // Now that we have modified User, add it back to the CSE maps. If it
6038 // already exists there, recursively merge the results together.
6039 AddModifiedNodeToCSEMaps(User);
6042 // If we just RAUW'd the root, take note.
6043 if (From == getRoot().getNode())
6044 setRoot(SDValue(To[getRoot().getResNo()]));
6047 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6048 /// uses of other values produced by From.getNode() alone. The Deleted
6049 /// vector is handled the same way as for ReplaceAllUsesWith.
6050 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6051 // Handle the really simple, really trivial case efficiently.
6052 if (From == To) return;
6054 // Handle the simple, trivial, case efficiently.
6055 if (From.getNode()->getNumValues() == 1) {
6056 ReplaceAllUsesWith(From, To);
6060 // Iterate over just the existing users of From. See the comments in
6061 // the ReplaceAllUsesWith above.
6062 SDNode::use_iterator UI = From.getNode()->use_begin(),
6063 UE = From.getNode()->use_end();
6064 RAUWUpdateListener Listener(*this, UI, UE);
6067 bool UserRemovedFromCSEMaps = false;
6069 // A user can appear in a use list multiple times, and when this
6070 // happens the uses are usually next to each other in the list.
6071 // To help reduce the number of CSE recomputations, process all
6072 // the uses of this user that we can find this way.
6074 SDUse &Use = UI.getUse();
6076 // Skip uses of different values from the same node.
6077 if (Use.getResNo() != From.getResNo()) {
6082 // If this node hasn't been modified yet, it's still in the CSE maps,
6083 // so remove its old self from the CSE maps.
6084 if (!UserRemovedFromCSEMaps) {
6085 RemoveNodeFromCSEMaps(User);
6086 UserRemovedFromCSEMaps = true;
6091 } while (UI != UE && *UI == User);
6093 // We are iterating over all uses of the From node, so if a use
6094 // doesn't use the specific value, no changes are made.
6095 if (!UserRemovedFromCSEMaps)
6098 // Now that we have modified User, add it back to the CSE maps. If it
6099 // already exists there, recursively merge the results together.
6100 AddModifiedNodeToCSEMaps(User);
6103 // If we just RAUW'd the root, take note.
6104 if (From == getRoot())
6109 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6110 /// to record information about a use.
6117 /// operator< - Sort Memos by User.
6118 bool operator<(const UseMemo &L, const UseMemo &R) {
6119 return (intptr_t)L.User < (intptr_t)R.User;
6123 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6124 /// uses of other values produced by From.getNode() alone. The same value
6125 /// may appear in both the From and To list. The Deleted vector is
6126 /// handled the same way as for ReplaceAllUsesWith.
6127 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6130 // Handle the simple, trivial case efficiently.
6132 return ReplaceAllUsesOfValueWith(*From, *To);
6134 // Read up all the uses and make records of them. This helps
6135 // processing new uses that are introduced during the
6136 // replacement process.
6137 SmallVector<UseMemo, 4> Uses;
6138 for (unsigned i = 0; i != Num; ++i) {
6139 unsigned FromResNo = From[i].getResNo();
6140 SDNode *FromNode = From[i].getNode();
6141 for (SDNode::use_iterator UI = FromNode->use_begin(),
6142 E = FromNode->use_end(); UI != E; ++UI) {
6143 SDUse &Use = UI.getUse();
6144 if (Use.getResNo() == FromResNo) {
6145 UseMemo Memo = { *UI, i, &Use };
6146 Uses.push_back(Memo);
6151 // Sort the uses, so that all the uses from a given User are together.
6152 std::sort(Uses.begin(), Uses.end());
6154 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6155 UseIndex != UseIndexEnd; ) {
6156 // We know that this user uses some value of From. If it is the right
6157 // value, update it.
6158 SDNode *User = Uses[UseIndex].User;
6160 // This node is about to morph, remove its old self from the CSE maps.
6161 RemoveNodeFromCSEMaps(User);
6163 // The Uses array is sorted, so all the uses for a given User
6164 // are next to each other in the list.
6165 // To help reduce the number of CSE recomputations, process all
6166 // the uses of this user that we can find this way.
6168 unsigned i = Uses[UseIndex].Index;
6169 SDUse &Use = *Uses[UseIndex].Use;
6173 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6175 // Now that we have modified User, add it back to the CSE maps. If it
6176 // already exists there, recursively merge the results together.
6177 AddModifiedNodeToCSEMaps(User);
6181 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6182 /// based on their topological order. It returns the maximum id and a vector
6183 /// of the SDNodes* in assigned order by reference.
6184 unsigned SelectionDAG::AssignTopologicalOrder() {
6186 unsigned DAGSize = 0;
6188 // SortedPos tracks the progress of the algorithm. Nodes before it are
6189 // sorted, nodes after it are unsorted. When the algorithm completes
6190 // it is at the end of the list.
6191 allnodes_iterator SortedPos = allnodes_begin();
6193 // Visit all the nodes. Move nodes with no operands to the front of
6194 // the list immediately. Annotate nodes that do have operands with their
6195 // operand count. Before we do this, the Node Id fields of the nodes
6196 // may contain arbitrary values. After, the Node Id fields for nodes
6197 // before SortedPos will contain the topological sort index, and the
6198 // Node Id fields for nodes At SortedPos and after will contain the
6199 // count of outstanding operands.
6200 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6202 checkForCycles(N, this);
6203 unsigned Degree = N->getNumOperands();
6205 // A node with no uses, add it to the result array immediately.
6206 N->setNodeId(DAGSize++);
6207 allnodes_iterator Q = N;
6209 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6210 assert(SortedPos != AllNodes.end() && "Overran node list");
6213 // Temporarily use the Node Id as scratch space for the degree count.
6214 N->setNodeId(Degree);
6218 // Visit all the nodes. As we iterate, move nodes into sorted order,
6219 // such that by the time the end is reached all nodes will be sorted.
6220 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6222 checkForCycles(N, this);
6223 // N is in sorted position, so all its uses have one less operand
6224 // that needs to be sorted.
6225 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6228 unsigned Degree = P->getNodeId();
6229 assert(Degree != 0 && "Invalid node degree");
6232 // All of P's operands are sorted, so P may sorted now.
6233 P->setNodeId(DAGSize++);
6235 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6236 assert(SortedPos != AllNodes.end() && "Overran node list");
6239 // Update P's outstanding operand count.
6240 P->setNodeId(Degree);
6243 if (I == SortedPos) {
6246 dbgs() << "Overran sorted position:\n";
6247 S->dumprFull(this); dbgs() << "\n";
6248 dbgs() << "Checking if this is due to cycles\n";
6249 checkForCycles(this, true);
6251 llvm_unreachable(nullptr);
6255 assert(SortedPos == AllNodes.end() &&
6256 "Topological sort incomplete!");
6257 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6258 "First node in topological sort is not the entry token!");
6259 assert(AllNodes.front().getNodeId() == 0 &&
6260 "First node in topological sort has non-zero id!");
6261 assert(AllNodes.front().getNumOperands() == 0 &&
6262 "First node in topological sort has operands!");
6263 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6264 "Last node in topologic sort has unexpected id!");
6265 assert(AllNodes.back().use_empty() &&
6266 "Last node in topologic sort has users!");
6267 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6271 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6272 /// value is produced by SD.
6273 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6275 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6276 SD->setHasDebugValue(true);
6278 DbgInfo->add(DB, SD, isParameter);
6281 /// TransferDbgValues - Transfer SDDbgValues.
6282 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6283 if (From == To || !From.getNode()->getHasDebugValue())
6285 SDNode *FromNode = From.getNode();
6286 SDNode *ToNode = To.getNode();
6287 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6288 SmallVector<SDDbgValue *, 2> ClonedDVs;
6289 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6291 SDDbgValue *Dbg = *I;
6292 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6294 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6295 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6296 Dbg->getDebugLoc(), Dbg->getOrder());
6297 ClonedDVs.push_back(Clone);
6300 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6301 E = ClonedDVs.end(); I != E; ++I)
6302 AddDbgValue(*I, ToNode, false);
6305 //===----------------------------------------------------------------------===//
6307 //===----------------------------------------------------------------------===//
6309 HandleSDNode::~HandleSDNode() {
6313 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6314 DebugLoc DL, const GlobalValue *GA,
6315 EVT VT, int64_t o, unsigned char TF)
6316 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6320 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6321 SDValue X, unsigned SrcAS,
6323 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6324 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6326 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6327 EVT memvt, MachineMemOperand *mmo)
6328 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6329 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6330 MMO->isNonTemporal(), MMO->isInvariant());
6331 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6332 assert(isNonTemporal() == MMO->isNonTemporal() &&
6333 "Non-temporal encoding error!");
6334 // We check here that the size of the memory operand fits within the size of
6335 // the MMO. This is because the MMO might indicate only a possible address
6336 // range instead of specifying the affected memory addresses precisely.
6337 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6340 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6341 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6342 : SDNode(Opc, Order, dl, VTs, Ops),
6343 MemoryVT(memvt), MMO(mmo) {
6344 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6345 MMO->isNonTemporal(), MMO->isInvariant());
6346 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6347 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6350 /// Profile - Gather unique data for the node.
6352 void SDNode::Profile(FoldingSetNodeID &ID) const {
6353 AddNodeIDNode(ID, this);
6358 std::vector<EVT> VTs;
6361 VTs.reserve(MVT::LAST_VALUETYPE);
6362 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6363 VTs.push_back(MVT((MVT::SimpleValueType)i));
6368 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6369 static ManagedStatic<EVTArray> SimpleVTArray;
6370 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6372 /// getValueTypeList - Return a pointer to the specified value type.
6374 const EVT *SDNode::getValueTypeList(EVT VT) {
6375 if (VT.isExtended()) {
6376 sys::SmartScopedLock<true> Lock(*VTMutex);
6377 return &(*EVTs->insert(VT).first);
6379 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6380 "Value type out of range!");
6381 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6385 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6386 /// indicated value. This method ignores uses of other values defined by this
6388 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6389 assert(Value < getNumValues() && "Bad value!");
6391 // TODO: Only iterate over uses of a given value of the node
6392 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6393 if (UI.getUse().getResNo() == Value) {
6400 // Found exactly the right number of uses?
6405 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6406 /// value. This method ignores uses of other values defined by this operation.
6407 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6408 assert(Value < getNumValues() && "Bad value!");
6410 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6411 if (UI.getUse().getResNo() == Value)
6418 /// isOnlyUserOf - Return true if this node is the only use of N.
6420 bool SDNode::isOnlyUserOf(SDNode *N) const {
6422 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6433 /// isOperand - Return true if this node is an operand of N.
6435 bool SDValue::isOperandOf(SDNode *N) const {
6436 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6437 if (*this == N->getOperand(i))
6442 bool SDNode::isOperandOf(SDNode *N) const {
6443 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6444 if (this == N->OperandList[i].getNode())
6449 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6450 /// be a chain) reaches the specified operand without crossing any
6451 /// side-effecting instructions on any chain path. In practice, this looks
6452 /// through token factors and non-volatile loads. In order to remain efficient,
6453 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6454 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6455 unsigned Depth) const {
6456 if (*this == Dest) return true;
6458 // Don't search too deeply, we just want to be able to see through
6459 // TokenFactor's etc.
6460 if (Depth == 0) return false;
6462 // If this is a token factor, all inputs to the TF happen in parallel. If any
6463 // of the operands of the TF does not reach dest, then we cannot do the xform.
6464 if (getOpcode() == ISD::TokenFactor) {
6465 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6466 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6471 // Loads don't have side effects, look through them.
6472 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6473 if (!Ld->isVolatile())
6474 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6479 /// hasPredecessor - Return true if N is a predecessor of this node.
6480 /// N is either an operand of this node, or can be reached by recursively
6481 /// traversing up the operands.
6482 /// NOTE: This is an expensive method. Use it carefully.
6483 bool SDNode::hasPredecessor(const SDNode *N) const {
6484 SmallPtrSet<const SDNode *, 32> Visited;
6485 SmallVector<const SDNode *, 16> Worklist;
6486 return hasPredecessorHelper(N, Visited, Worklist);
6490 SDNode::hasPredecessorHelper(const SDNode *N,
6491 SmallPtrSetImpl<const SDNode *> &Visited,
6492 SmallVectorImpl<const SDNode *> &Worklist) const {
6493 if (Visited.empty()) {
6494 Worklist.push_back(this);
6496 // Take a look in the visited set. If we've already encountered this node
6497 // we needn't search further.
6498 if (Visited.count(N))
6502 // Haven't visited N yet. Continue the search.
6503 while (!Worklist.empty()) {
6504 const SDNode *M = Worklist.pop_back_val();
6505 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6506 SDNode *Op = M->getOperand(i).getNode();
6507 if (Visited.insert(Op).second)
6508 Worklist.push_back(Op);
6517 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6518 assert(Num < NumOperands && "Invalid child # of SDNode!");
6519 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6522 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6523 assert(N->getNumValues() == 1 &&
6524 "Can't unroll a vector with multiple results!");
6526 EVT VT = N->getValueType(0);
6527 unsigned NE = VT.getVectorNumElements();
6528 EVT EltVT = VT.getVectorElementType();
6531 SmallVector<SDValue, 8> Scalars;
6532 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6534 // If ResNE is 0, fully unroll the vector op.
6537 else if (NE > ResNE)
6541 for (i= 0; i != NE; ++i) {
6542 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6543 SDValue Operand = N->getOperand(j);
6544 EVT OperandVT = Operand.getValueType();
6545 if (OperandVT.isVector()) {
6546 // A vector operand; extract a single element.
6547 EVT OperandEltVT = OperandVT.getVectorElementType();
6548 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6551 getConstant(i, TLI->getVectorIdxTy()));
6553 // A scalar operand; just use it as is.
6554 Operands[j] = Operand;
6558 switch (N->getOpcode()) {
6560 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6563 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6570 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6571 getShiftAmountOperand(Operands[0].getValueType(),
6574 case ISD::SIGN_EXTEND_INREG:
6575 case ISD::FP_ROUND_INREG: {
6576 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6577 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6579 getValueType(ExtVT)));
6584 for (; i < ResNE; ++i)
6585 Scalars.push_back(getUNDEF(EltVT));
6587 return getNode(ISD::BUILD_VECTOR, dl,
6588 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6592 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6593 /// location that is 'Dist' units away from the location that the 'Base' load
6594 /// is loading from.
6595 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6596 unsigned Bytes, int Dist) const {
6597 if (LD->getChain() != Base->getChain())
6599 EVT VT = LD->getValueType(0);
6600 if (VT.getSizeInBits() / 8 != Bytes)
6603 SDValue Loc = LD->getOperand(1);
6604 SDValue BaseLoc = Base->getOperand(1);
6605 if (Loc.getOpcode() == ISD::FrameIndex) {
6606 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6608 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6609 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6610 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6611 int FS = MFI->getObjectSize(FI);
6612 int BFS = MFI->getObjectSize(BFI);
6613 if (FS != BFS || FS != (int)Bytes) return false;
6614 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6618 if (isBaseWithConstantOffset(Loc)) {
6619 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6620 if (Loc.getOperand(0) == BaseLoc) {
6621 // If the base location is a simple address with no offset itself, then
6622 // the second load's first add operand should be the base address.
6623 if (LocOffset == Dist * (int)Bytes)
6625 } else if (isBaseWithConstantOffset(BaseLoc)) {
6626 // The base location itself has an offset, so subtract that value from the
6627 // second load's offset before comparing to distance * size.
6629 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6630 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6631 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6636 const GlobalValue *GV1 = nullptr;
6637 const GlobalValue *GV2 = nullptr;
6638 int64_t Offset1 = 0;
6639 int64_t Offset2 = 0;
6640 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6641 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6642 if (isGA1 && isGA2 && GV1 == GV2)
6643 return Offset1 == (Offset2 + Dist*Bytes);
6648 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6649 /// it cannot be inferred.
6650 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6651 // If this is a GlobalAddress + cst, return the alignment.
6652 const GlobalValue *GV;
6653 int64_t GVOffset = 0;
6654 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6655 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6656 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6657 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6658 TLI->getDataLayout());
6659 unsigned AlignBits = KnownZero.countTrailingOnes();
6660 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6662 return MinAlign(Align, GVOffset);
6665 // If this is a direct reference to a stack slot, use information about the
6666 // stack slot's alignment.
6667 int FrameIdx = 1 << 31;
6668 int64_t FrameOffset = 0;
6669 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6670 FrameIdx = FI->getIndex();
6671 } else if (isBaseWithConstantOffset(Ptr) &&
6672 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6674 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6675 FrameOffset = Ptr.getConstantOperandVal(1);
6678 if (FrameIdx != (1 << 31)) {
6679 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6680 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6688 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6689 /// which is split (or expanded) into two not necessarily identical pieces.
6690 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6691 // Currently all types are split in half.
6693 if (!VT.isVector()) {
6694 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6696 unsigned NumElements = VT.getVectorNumElements();
6697 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6698 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6701 return std::make_pair(LoVT, HiVT);
6704 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6706 std::pair<SDValue, SDValue>
6707 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6709 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6710 N.getValueType().getVectorNumElements() &&
6711 "More vector elements requested than available!");
6713 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6714 getConstant(0, TLI->getVectorIdxTy()));
6715 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6716 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6717 return std::make_pair(Lo, Hi);
6720 void SelectionDAG::ExtractVectorElements(SDValue Op,
6721 SmallVectorImpl<SDValue> &Args,
6722 unsigned Start, unsigned Count) {
6723 EVT VT = Op.getValueType();
6725 Count = VT.getVectorNumElements();
6727 EVT EltVT = VT.getVectorElementType();
6728 EVT IdxTy = TLI->getVectorIdxTy();
6730 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6731 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6732 Op, getConstant(i, IdxTy)));
6736 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6737 unsigned GlobalAddressSDNode::getAddressSpace() const {
6738 return getGlobal()->getType()->getAddressSpace();
6742 Type *ConstantPoolSDNode::getType() const {
6743 if (isMachineConstantPoolEntry())
6744 return Val.MachineCPVal->getType();
6745 return Val.ConstVal->getType();
6748 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6750 unsigned &SplatBitSize,
6752 unsigned MinSplatBits,
6753 bool isBigEndian) const {
6754 EVT VT = getValueType(0);
6755 assert(VT.isVector() && "Expected a vector type");
6756 unsigned sz = VT.getSizeInBits();
6757 if (MinSplatBits > sz)
6760 SplatValue = APInt(sz, 0);
6761 SplatUndef = APInt(sz, 0);
6763 // Get the bits. Bits with undefined values (when the corresponding element
6764 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6765 // in SplatValue. If any of the values are not constant, give up and return
6767 unsigned int nOps = getNumOperands();
6768 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6769 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6771 for (unsigned j = 0; j < nOps; ++j) {
6772 unsigned i = isBigEndian ? nOps-1-j : j;
6773 SDValue OpVal = getOperand(i);
6774 unsigned BitPos = j * EltBitSize;
6776 if (OpVal.getOpcode() == ISD::UNDEF)
6777 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6778 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6779 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6780 zextOrTrunc(sz) << BitPos;
6781 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6782 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6787 // The build_vector is all constants or undefs. Find the smallest element
6788 // size that splats the vector.
6790 HasAnyUndefs = (SplatUndef != 0);
6793 unsigned HalfSize = sz / 2;
6794 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6795 APInt LowValue = SplatValue.trunc(HalfSize);
6796 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6797 APInt LowUndef = SplatUndef.trunc(HalfSize);
6799 // If the two halves do not match (ignoring undef bits), stop here.
6800 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6801 MinSplatBits > HalfSize)
6804 SplatValue = HighValue | LowValue;
6805 SplatUndef = HighUndef & LowUndef;
6814 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6815 if (UndefElements) {
6816 UndefElements->clear();
6817 UndefElements->resize(getNumOperands());
6820 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6821 SDValue Op = getOperand(i);
6822 if (Op.getOpcode() == ISD::UNDEF) {
6824 (*UndefElements)[i] = true;
6825 } else if (!Splatted) {
6827 } else if (Splatted != Op) {
6833 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6834 "Can only have a splat without a constant for all undefs.");
6835 return getOperand(0);
6842 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6843 return dyn_cast_or_null<ConstantSDNode>(
6844 getSplatValue(UndefElements).getNode());
6848 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6849 return dyn_cast_or_null<ConstantFPSDNode>(
6850 getSplatValue(UndefElements).getNode());
6853 bool BuildVectorSDNode::isConstant() const {
6854 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6855 unsigned Opc = getOperand(i).getOpcode();
6856 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6862 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6863 // Find the first non-undef value in the shuffle mask.
6865 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6868 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6870 // Make sure all remaining elements are either undef or the same as the first
6872 for (int Idx = Mask[i]; i != e; ++i)
6873 if (Mask[i] >= 0 && Mask[i] != Idx)
6879 static void checkForCyclesHelper(const SDNode *N,
6880 SmallPtrSetImpl<const SDNode*> &Visited,
6881 SmallPtrSetImpl<const SDNode*> &Checked,
6882 const llvm::SelectionDAG *DAG) {
6883 // If this node has already been checked, don't check it again.
6884 if (Checked.count(N))
6887 // If a node has already been visited on this depth-first walk, reject it as
6889 if (!Visited.insert(N).second) {
6890 errs() << "Detected cycle in SelectionDAG\n";
6891 dbgs() << "Offending node:\n";
6892 N->dumprFull(DAG); dbgs() << "\n";
6896 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6897 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6904 void llvm::checkForCycles(const llvm::SDNode *N,
6905 const llvm::SelectionDAG *DAG,
6913 assert(N && "Checking nonexistent SDNode");
6914 SmallPtrSet<const SDNode*, 32> visited;
6915 SmallPtrSet<const SDNode*, 32> checked;
6916 checkForCyclesHelper(N, visited, checked, DAG);
6921 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6922 checkForCycles(DAG->getRoot().getNode(), DAG, force);