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);
1541 // We only have a splat which can skip shuffles if there is a splatted
1542 // value and no undef lanes rearranged by the shuffle.
1543 if (Splat && UndefElements.none()) {
1544 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1545 // number of elements match or the value splatted is a zero constant.
1546 if (V.getValueType().getVectorNumElements() ==
1547 VT.getVectorNumElements())
1549 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1550 if (C->isNullValue())
1554 // If the shuffle itself creates a constant splat, build the vector
1557 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1558 if (isa<ConstantSDNode>(Splatted) || isa<ConstantFPSDNode>(Splatted)) {
1559 SmallVector<SDValue, 8> Ops;
1560 for (unsigned i = 0; i != NElts; ++i) {
1561 Ops.push_back(Splatted);
1563 SDValue &NewBV = getNode(ISD::BUILD_VECTOR, dl,
1564 BV->getValueType(0), Ops);
1566 // We may have jumped through bitcasts, so the type of the
1567 // BUILD_VECTOR may not match the type of the shuffle.
1568 if (BV->getValueType(0) != VT)
1569 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1576 FoldingSetNodeID ID;
1577 SDValue Ops[2] = { N1, N2 };
1578 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1579 for (unsigned i = 0; i != NElts; ++i)
1580 ID.AddInteger(MaskVec[i]);
1583 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1584 return SDValue(E, 0);
1586 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1587 // SDNode doesn't have access to it. This memory will be "leaked" when
1588 // the node is deallocated, but recovered when the NodeAllocator is released.
1589 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1590 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1592 ShuffleVectorSDNode *N =
1593 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1594 dl.getDebugLoc(), N1, N2,
1596 CSEMap.InsertNode(N, IP);
1598 return SDValue(N, 0);
1601 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1602 MVT VT = SV.getSimpleValueType(0);
1603 unsigned NumElems = VT.getVectorNumElements();
1604 SmallVector<int, 8> MaskVec;
1606 for (unsigned i = 0; i != NumElems; ++i) {
1607 int Idx = SV.getMaskElt(i);
1609 if (Idx < (int)NumElems)
1614 MaskVec.push_back(Idx);
1617 SDValue Op0 = SV.getOperand(0);
1618 SDValue Op1 = SV.getOperand(1);
1619 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1622 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1623 SDValue Val, SDValue DTy,
1624 SDValue STy, SDValue Rnd, SDValue Sat,
1625 ISD::CvtCode Code) {
1626 // If the src and dest types are the same and the conversion is between
1627 // integer types of the same sign or two floats, no conversion is necessary.
1629 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1632 FoldingSetNodeID ID;
1633 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1634 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1636 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1637 return SDValue(E, 0);
1639 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1642 CSEMap.InsertNode(N, IP);
1644 return SDValue(N, 0);
1647 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1648 FoldingSetNodeID ID;
1649 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1650 ID.AddInteger(RegNo);
1652 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1653 return SDValue(E, 0);
1655 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1656 CSEMap.InsertNode(N, IP);
1658 return SDValue(N, 0);
1661 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1662 FoldingSetNodeID ID;
1663 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1664 ID.AddPointer(RegMask);
1666 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1667 return SDValue(E, 0);
1669 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1670 CSEMap.InsertNode(N, IP);
1672 return SDValue(N, 0);
1675 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1676 FoldingSetNodeID ID;
1677 SDValue Ops[] = { Root };
1678 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1679 ID.AddPointer(Label);
1681 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1682 return SDValue(E, 0);
1684 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1685 dl.getDebugLoc(), Root, Label);
1686 CSEMap.InsertNode(N, IP);
1688 return SDValue(N, 0);
1692 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1695 unsigned char TargetFlags) {
1696 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1698 FoldingSetNodeID ID;
1699 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1701 ID.AddInteger(Offset);
1702 ID.AddInteger(TargetFlags);
1704 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1705 return SDValue(E, 0);
1707 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1709 CSEMap.InsertNode(N, IP);
1711 return SDValue(N, 0);
1714 SDValue SelectionDAG::getSrcValue(const Value *V) {
1715 assert((!V || V->getType()->isPointerTy()) &&
1716 "SrcValue is not a pointer?");
1718 FoldingSetNodeID ID;
1719 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1723 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1724 return SDValue(E, 0);
1726 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1727 CSEMap.InsertNode(N, IP);
1729 return SDValue(N, 0);
1732 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1733 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1734 FoldingSetNodeID ID;
1735 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1739 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1740 return SDValue(E, 0);
1742 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1743 CSEMap.InsertNode(N, IP);
1745 return SDValue(N, 0);
1748 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1749 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1750 unsigned SrcAS, unsigned DestAS) {
1751 SDValue Ops[] = {Ptr};
1752 FoldingSetNodeID ID;
1753 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1754 ID.AddInteger(SrcAS);
1755 ID.AddInteger(DestAS);
1758 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1759 return SDValue(E, 0);
1761 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1763 VT, Ptr, SrcAS, DestAS);
1764 CSEMap.InsertNode(N, IP);
1766 return SDValue(N, 0);
1769 /// getShiftAmountOperand - Return the specified value casted to
1770 /// the target's desired shift amount type.
1771 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1772 EVT OpTy = Op.getValueType();
1773 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1774 if (OpTy == ShTy || OpTy.isVector()) return Op;
1776 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1777 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1780 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1781 /// specified value type.
1782 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1783 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1784 unsigned ByteSize = VT.getStoreSize();
1785 Type *Ty = VT.getTypeForEVT(*getContext());
1786 unsigned StackAlign =
1787 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1789 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1790 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1793 /// CreateStackTemporary - Create a stack temporary suitable for holding
1794 /// either of the specified value types.
1795 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1796 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1797 VT2.getStoreSizeInBits())/8;
1798 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1799 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1800 const DataLayout *TD = TLI->getDataLayout();
1801 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1802 TD->getPrefTypeAlignment(Ty2));
1804 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1805 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1806 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1809 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1810 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1811 // These setcc operations always fold.
1815 case ISD::SETFALSE2: return getConstant(0, VT);
1817 case ISD::SETTRUE2: {
1818 TargetLowering::BooleanContent Cnt =
1819 TLI->getBooleanContents(N1->getValueType(0));
1821 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1834 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1838 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1839 const APInt &C2 = N2C->getAPIntValue();
1840 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1841 const APInt &C1 = N1C->getAPIntValue();
1844 default: llvm_unreachable("Unknown integer setcc!");
1845 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1846 case ISD::SETNE: return getConstant(C1 != C2, VT);
1847 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1848 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1849 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1850 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1851 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1852 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1853 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1854 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1858 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1859 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1860 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1863 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1864 return getUNDEF(VT);
1866 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1867 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1868 return getUNDEF(VT);
1870 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1871 R==APFloat::cmpLessThan, VT);
1872 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1873 return getUNDEF(VT);
1875 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1876 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1877 return getUNDEF(VT);
1879 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1880 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1881 return getUNDEF(VT);
1883 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1884 R==APFloat::cmpEqual, VT);
1885 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1886 return getUNDEF(VT);
1888 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1889 R==APFloat::cmpEqual, VT);
1890 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1891 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1892 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1893 R==APFloat::cmpEqual, VT);
1894 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1895 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1896 R==APFloat::cmpLessThan, VT);
1897 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1898 R==APFloat::cmpUnordered, VT);
1899 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1900 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1903 // Ensure that the constant occurs on the RHS.
1904 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1905 MVT CompVT = N1.getValueType().getSimpleVT();
1906 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1909 return getSetCC(dl, VT, N2, N1, SwappedCond);
1913 // Could not fold it.
1917 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1918 /// use this predicate to simplify operations downstream.
1919 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1920 // This predicate is not safe for vector operations.
1921 if (Op.getValueType().isVector())
1924 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1925 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1928 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1929 /// this predicate to simplify operations downstream. Mask is known to be zero
1930 /// for bits that V cannot have.
1931 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1932 unsigned Depth) const {
1933 APInt KnownZero, KnownOne;
1934 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1935 return (KnownZero & Mask) == Mask;
1938 /// Determine which bits of Op are known to be either zero or one and return
1939 /// them in the KnownZero/KnownOne bitsets.
1940 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1941 APInt &KnownOne, unsigned Depth) const {
1942 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1944 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1946 return; // Limit search depth.
1948 APInt KnownZero2, KnownOne2;
1950 switch (Op.getOpcode()) {
1952 // We know all of the bits for a constant!
1953 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1954 KnownZero = ~KnownOne;
1957 // If either the LHS or the RHS are Zero, the result is zero.
1958 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1959 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1961 // Output known-1 bits are only known if set in both the LHS & RHS.
1962 KnownOne &= KnownOne2;
1963 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1964 KnownZero |= KnownZero2;
1967 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1968 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1970 // Output known-0 bits are only known if clear in both the LHS & RHS.
1971 KnownZero &= KnownZero2;
1972 // Output known-1 are known to be set if set in either the LHS | RHS.
1973 KnownOne |= KnownOne2;
1976 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1977 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1979 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1980 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1981 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1982 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1983 KnownZero = KnownZeroOut;
1987 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1988 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1990 // If low bits are zero in either operand, output low known-0 bits.
1991 // Also compute a conserative estimate for high known-0 bits.
1992 // More trickiness is possible, but this is sufficient for the
1993 // interesting case of alignment computation.
1994 KnownOne.clearAllBits();
1995 unsigned TrailZ = KnownZero.countTrailingOnes() +
1996 KnownZero2.countTrailingOnes();
1997 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1998 KnownZero2.countLeadingOnes(),
1999 BitWidth) - BitWidth;
2001 TrailZ = std::min(TrailZ, BitWidth);
2002 LeadZ = std::min(LeadZ, BitWidth);
2003 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2004 APInt::getHighBitsSet(BitWidth, LeadZ);
2008 // For the purposes of computing leading zeros we can conservatively
2009 // treat a udiv as a logical right shift by the power of 2 known to
2010 // be less than the denominator.
2011 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2012 unsigned LeadZ = KnownZero2.countLeadingOnes();
2014 KnownOne2.clearAllBits();
2015 KnownZero2.clearAllBits();
2016 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2017 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2018 if (RHSUnknownLeadingOnes != BitWidth)
2019 LeadZ = std::min(BitWidth,
2020 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2022 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2026 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2027 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2029 // Only known if known in both the LHS and RHS.
2030 KnownOne &= KnownOne2;
2031 KnownZero &= KnownZero2;
2033 case ISD::SELECT_CC:
2034 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2035 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2037 // Only known if known in both the LHS and RHS.
2038 KnownOne &= KnownOne2;
2039 KnownZero &= KnownZero2;
2047 if (Op.getResNo() != 1)
2049 // The boolean result conforms to getBooleanContents.
2050 // If we know the result of a setcc has the top bits zero, use this info.
2051 // We know that we have an integer-based boolean since these operations
2052 // are only available for integer.
2053 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2054 TargetLowering::ZeroOrOneBooleanContent &&
2056 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2059 // If we know the result of a setcc has the top bits zero, use this info.
2060 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2061 TargetLowering::ZeroOrOneBooleanContent &&
2063 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2066 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2067 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2068 unsigned ShAmt = SA->getZExtValue();
2070 // If the shift count is an invalid immediate, don't do anything.
2071 if (ShAmt >= BitWidth)
2074 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2075 KnownZero <<= ShAmt;
2077 // low bits known zero.
2078 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2082 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2083 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2084 unsigned ShAmt = SA->getZExtValue();
2086 // If the shift count is an invalid immediate, don't do anything.
2087 if (ShAmt >= BitWidth)
2090 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2091 KnownZero = KnownZero.lshr(ShAmt);
2092 KnownOne = KnownOne.lshr(ShAmt);
2094 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2095 KnownZero |= HighBits; // High bits known zero.
2099 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2100 unsigned ShAmt = SA->getZExtValue();
2102 // If the shift count is an invalid immediate, don't do anything.
2103 if (ShAmt >= BitWidth)
2106 // If any of the demanded bits are produced by the sign extension, we also
2107 // demand the input sign bit.
2108 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2110 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2111 KnownZero = KnownZero.lshr(ShAmt);
2112 KnownOne = KnownOne.lshr(ShAmt);
2114 // Handle the sign bits.
2115 APInt SignBit = APInt::getSignBit(BitWidth);
2116 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2118 if (KnownZero.intersects(SignBit)) {
2119 KnownZero |= HighBits; // New bits are known zero.
2120 } else if (KnownOne.intersects(SignBit)) {
2121 KnownOne |= HighBits; // New bits are known one.
2125 case ISD::SIGN_EXTEND_INREG: {
2126 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2127 unsigned EBits = EVT.getScalarType().getSizeInBits();
2129 // Sign extension. Compute the demanded bits in the result that are not
2130 // present in the input.
2131 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2133 APInt InSignBit = APInt::getSignBit(EBits);
2134 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2136 // If the sign extended bits are demanded, we know that the sign
2138 InSignBit = InSignBit.zext(BitWidth);
2139 if (NewBits.getBoolValue())
2140 InputDemandedBits |= InSignBit;
2142 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2143 KnownOne &= InputDemandedBits;
2144 KnownZero &= InputDemandedBits;
2146 // If the sign bit of the input is known set or clear, then we know the
2147 // top bits of the result.
2148 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2149 KnownZero |= NewBits;
2150 KnownOne &= ~NewBits;
2151 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2152 KnownOne |= NewBits;
2153 KnownZero &= ~NewBits;
2154 } else { // Input sign bit unknown
2155 KnownZero &= ~NewBits;
2156 KnownOne &= ~NewBits;
2161 case ISD::CTTZ_ZERO_UNDEF:
2163 case ISD::CTLZ_ZERO_UNDEF:
2165 unsigned LowBits = Log2_32(BitWidth)+1;
2166 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2167 KnownOne.clearAllBits();
2171 LoadSDNode *LD = cast<LoadSDNode>(Op);
2172 // If this is a ZEXTLoad and we are looking at the loaded value.
2173 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2174 EVT VT = LD->getMemoryVT();
2175 unsigned MemBits = VT.getScalarType().getSizeInBits();
2176 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2177 } else if (const MDNode *Ranges = LD->getRanges()) {
2178 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2182 case ISD::ZERO_EXTEND: {
2183 EVT InVT = Op.getOperand(0).getValueType();
2184 unsigned InBits = InVT.getScalarType().getSizeInBits();
2185 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2186 KnownZero = KnownZero.trunc(InBits);
2187 KnownOne = KnownOne.trunc(InBits);
2188 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2189 KnownZero = KnownZero.zext(BitWidth);
2190 KnownOne = KnownOne.zext(BitWidth);
2191 KnownZero |= NewBits;
2194 case ISD::SIGN_EXTEND: {
2195 EVT InVT = Op.getOperand(0).getValueType();
2196 unsigned InBits = InVT.getScalarType().getSizeInBits();
2197 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2199 KnownZero = KnownZero.trunc(InBits);
2200 KnownOne = KnownOne.trunc(InBits);
2201 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2203 // Note if the sign bit is known to be zero or one.
2204 bool SignBitKnownZero = KnownZero.isNegative();
2205 bool SignBitKnownOne = KnownOne.isNegative();
2207 KnownZero = KnownZero.zext(BitWidth);
2208 KnownOne = KnownOne.zext(BitWidth);
2210 // If the sign bit is known zero or one, the top bits match.
2211 if (SignBitKnownZero)
2212 KnownZero |= NewBits;
2213 else if (SignBitKnownOne)
2214 KnownOne |= NewBits;
2217 case ISD::ANY_EXTEND: {
2218 EVT InVT = Op.getOperand(0).getValueType();
2219 unsigned InBits = InVT.getScalarType().getSizeInBits();
2220 KnownZero = KnownZero.trunc(InBits);
2221 KnownOne = KnownOne.trunc(InBits);
2222 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2223 KnownZero = KnownZero.zext(BitWidth);
2224 KnownOne = KnownOne.zext(BitWidth);
2227 case ISD::TRUNCATE: {
2228 EVT InVT = Op.getOperand(0).getValueType();
2229 unsigned InBits = InVT.getScalarType().getSizeInBits();
2230 KnownZero = KnownZero.zext(InBits);
2231 KnownOne = KnownOne.zext(InBits);
2232 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2233 KnownZero = KnownZero.trunc(BitWidth);
2234 KnownOne = KnownOne.trunc(BitWidth);
2237 case ISD::AssertZext: {
2238 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2239 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2240 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2241 KnownZero |= (~InMask);
2242 KnownOne &= (~KnownZero);
2246 // All bits are zero except the low bit.
2247 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2251 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2252 // We know that the top bits of C-X are clear if X contains less bits
2253 // than C (i.e. no wrap-around can happen). For example, 20-X is
2254 // positive if we can prove that X is >= 0 and < 16.
2255 if (CLHS->getAPIntValue().isNonNegative()) {
2256 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2257 // NLZ can't be BitWidth with no sign bit
2258 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2259 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2261 // If all of the MaskV bits are known to be zero, then we know the
2262 // output top bits are zero, because we now know that the output is
2264 if ((KnownZero2 & MaskV) == MaskV) {
2265 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2266 // Top bits known zero.
2267 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2275 // Output known-0 bits are known if clear or set in both the low clear bits
2276 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2277 // low 3 bits clear.
2278 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2279 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2281 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2282 KnownZeroOut = std::min(KnownZeroOut,
2283 KnownZero2.countTrailingOnes());
2285 if (Op.getOpcode() == ISD::ADD) {
2286 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2290 // With ADDE, a carry bit may be added in, so we can only use this
2291 // information if we know (at least) that the low two bits are clear. We
2292 // then return to the caller that the low bit is unknown but that other bits
2294 if (KnownZeroOut >= 2) // ADDE
2295 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2299 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2300 const APInt &RA = Rem->getAPIntValue().abs();
2301 if (RA.isPowerOf2()) {
2302 APInt LowBits = RA - 1;
2303 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2305 // The low bits of the first operand are unchanged by the srem.
2306 KnownZero = KnownZero2 & LowBits;
2307 KnownOne = KnownOne2 & LowBits;
2309 // If the first operand is non-negative or has all low bits zero, then
2310 // the upper bits are all zero.
2311 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2312 KnownZero |= ~LowBits;
2314 // If the first operand is negative and not all low bits are zero, then
2315 // the upper bits are all one.
2316 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2317 KnownOne |= ~LowBits;
2318 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2323 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2324 const APInt &RA = Rem->getAPIntValue();
2325 if (RA.isPowerOf2()) {
2326 APInt LowBits = (RA - 1);
2327 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2329 // The upper bits are all zero, the lower ones are unchanged.
2330 KnownZero = KnownZero2 | ~LowBits;
2331 KnownOne = KnownOne2 & LowBits;
2336 // Since the result is less than or equal to either operand, any leading
2337 // zero bits in either operand must also exist in the result.
2338 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2339 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2341 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2342 KnownZero2.countLeadingOnes());
2343 KnownOne.clearAllBits();
2344 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2347 case ISD::FrameIndex:
2348 case ISD::TargetFrameIndex:
2349 if (unsigned Align = InferPtrAlignment(Op)) {
2350 // The low bits are known zero if the pointer is aligned.
2351 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2357 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2360 case ISD::INTRINSIC_WO_CHAIN:
2361 case ISD::INTRINSIC_W_CHAIN:
2362 case ISD::INTRINSIC_VOID:
2363 // Allow the target to implement this method for its nodes.
2364 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2368 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2371 /// ComputeNumSignBits - Return the number of times the sign bit of the
2372 /// register is replicated into the other bits. We know that at least 1 bit
2373 /// is always equal to the sign bit (itself), but other cases can give us
2374 /// information. For example, immediately after an "SRA X, 2", we know that
2375 /// the top 3 bits are all equal to each other, so we return 3.
2376 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2377 EVT VT = Op.getValueType();
2378 assert(VT.isInteger() && "Invalid VT!");
2379 unsigned VTBits = VT.getScalarType().getSizeInBits();
2381 unsigned FirstAnswer = 1;
2384 return 1; // Limit search depth.
2386 switch (Op.getOpcode()) {
2388 case ISD::AssertSext:
2389 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2390 return VTBits-Tmp+1;
2391 case ISD::AssertZext:
2392 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2395 case ISD::Constant: {
2396 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2397 return Val.getNumSignBits();
2400 case ISD::SIGN_EXTEND:
2402 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2403 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2405 case ISD::SIGN_EXTEND_INREG:
2406 // Max of the input and what this extends.
2408 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2411 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2412 return std::max(Tmp, Tmp2);
2415 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2416 // SRA X, C -> adds C sign bits.
2417 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2418 Tmp += C->getZExtValue();
2419 if (Tmp > VTBits) Tmp = VTBits;
2423 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2424 // shl destroys sign bits.
2425 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2426 if (C->getZExtValue() >= VTBits || // Bad shift.
2427 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2428 return Tmp - C->getZExtValue();
2433 case ISD::XOR: // NOT is handled here.
2434 // Logical binary ops preserve the number of sign bits at the worst.
2435 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2437 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2438 FirstAnswer = std::min(Tmp, Tmp2);
2439 // We computed what we know about the sign bits as our first
2440 // answer. Now proceed to the generic code that uses
2441 // computeKnownBits, and pick whichever answer is better.
2446 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2447 if (Tmp == 1) return 1; // Early out.
2448 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2449 return std::min(Tmp, Tmp2);
2457 if (Op.getResNo() != 1)
2459 // The boolean result conforms to getBooleanContents. Fall through.
2460 // If setcc returns 0/-1, all bits are sign bits.
2461 // We know that we have an integer-based boolean since these operations
2462 // are only available for integer.
2463 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2464 TargetLowering::ZeroOrNegativeOneBooleanContent)
2468 // If setcc returns 0/-1, all bits are sign bits.
2469 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2470 TargetLowering::ZeroOrNegativeOneBooleanContent)
2475 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2476 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2478 // Handle rotate right by N like a rotate left by 32-N.
2479 if (Op.getOpcode() == ISD::ROTR)
2480 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2482 // If we aren't rotating out all of the known-in sign bits, return the
2483 // number that are left. This handles rotl(sext(x), 1) for example.
2484 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2485 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2489 // Add can have at most one carry bit. Thus we know that the output
2490 // is, at worst, one more bit than the inputs.
2491 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2492 if (Tmp == 1) return 1; // Early out.
2494 // Special case decrementing a value (ADD X, -1):
2495 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2496 if (CRHS->isAllOnesValue()) {
2497 APInt KnownZero, KnownOne;
2498 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2500 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2502 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2505 // If we are subtracting one from a positive number, there is no carry
2506 // out of the result.
2507 if (KnownZero.isNegative())
2511 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2512 if (Tmp2 == 1) return 1;
2513 return std::min(Tmp, Tmp2)-1;
2516 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2517 if (Tmp2 == 1) return 1;
2520 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2521 if (CLHS->isNullValue()) {
2522 APInt KnownZero, KnownOne;
2523 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2524 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2526 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2529 // If the input is known to be positive (the sign bit is known clear),
2530 // the output of the NEG has the same number of sign bits as the input.
2531 if (KnownZero.isNegative())
2534 // Otherwise, we treat this like a SUB.
2537 // Sub can have at most one carry bit. Thus we know that the output
2538 // is, at worst, one more bit than the inputs.
2539 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2540 if (Tmp == 1) return 1; // Early out.
2541 return std::min(Tmp, Tmp2)-1;
2543 // FIXME: it's tricky to do anything useful for this, but it is an important
2544 // case for targets like X86.
2548 // If we are looking at the loaded value of the SDNode.
2549 if (Op.getResNo() == 0) {
2550 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2551 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2552 unsigned ExtType = LD->getExtensionType();
2555 case ISD::SEXTLOAD: // '17' bits known
2556 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2557 return VTBits-Tmp+1;
2558 case ISD::ZEXTLOAD: // '16' bits known
2559 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2565 // Allow the target to implement this method for its nodes.
2566 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2567 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2568 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2569 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2570 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2571 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2574 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2575 // use this information.
2576 APInt KnownZero, KnownOne;
2577 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2580 if (KnownZero.isNegative()) { // sign bit is 0
2582 } else if (KnownOne.isNegative()) { // sign bit is 1;
2589 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2590 // the number of identical bits in the top of the input value.
2592 Mask <<= Mask.getBitWidth()-VTBits;
2593 // Return # leading zeros. We use 'min' here in case Val was zero before
2594 // shifting. We don't want to return '64' as for an i32 "0".
2595 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2598 /// isBaseWithConstantOffset - Return true if the specified operand is an
2599 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2600 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2601 /// semantics as an ADD. This handles the equivalence:
2602 /// X|Cst == X+Cst iff X&Cst = 0.
2603 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2604 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2605 !isa<ConstantSDNode>(Op.getOperand(1)))
2608 if (Op.getOpcode() == ISD::OR &&
2609 !MaskedValueIsZero(Op.getOperand(0),
2610 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2617 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2618 // If we're told that NaNs won't happen, assume they won't.
2619 if (getTarget().Options.NoNaNsFPMath)
2622 // If the value is a constant, we can obviously see if it is a NaN or not.
2623 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2624 return !C->getValueAPF().isNaN();
2626 // TODO: Recognize more cases here.
2631 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2632 // If the value is a constant, we can obviously see if it is a zero or not.
2633 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2634 return !C->isZero();
2636 // TODO: Recognize more cases here.
2637 switch (Op.getOpcode()) {
2640 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2641 return !C->isNullValue();
2648 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2649 // Check the obvious case.
2650 if (A == B) return true;
2652 // For for negative and positive zero.
2653 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2654 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2655 if (CA->isZero() && CB->isZero()) return true;
2657 // Otherwise they may not be equal.
2661 /// getNode - Gets or creates the specified node.
2663 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2664 FoldingSetNodeID ID;
2665 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2667 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2668 return SDValue(E, 0);
2670 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2671 DL.getDebugLoc(), getVTList(VT));
2672 CSEMap.InsertNode(N, IP);
2675 return SDValue(N, 0);
2678 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2679 EVT VT, SDValue Operand) {
2680 // Constant fold unary operations with an integer constant operand. Even
2681 // opaque constant will be folded, because the folding of unary operations
2682 // doesn't create new constants with different values. Nevertheless, the
2683 // opaque flag is preserved during folding to prevent future folding with
2685 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2686 const APInt &Val = C->getAPIntValue();
2689 case ISD::SIGN_EXTEND:
2690 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2691 C->isTargetOpcode(), C->isOpaque());
2692 case ISD::ANY_EXTEND:
2693 case ISD::ZERO_EXTEND:
2695 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2696 C->isTargetOpcode(), C->isOpaque());
2697 case ISD::UINT_TO_FP:
2698 case ISD::SINT_TO_FP: {
2699 APFloat apf(EVTToAPFloatSemantics(VT),
2700 APInt::getNullValue(VT.getSizeInBits()));
2701 (void)apf.convertFromAPInt(Val,
2702 Opcode==ISD::SINT_TO_FP,
2703 APFloat::rmNearestTiesToEven);
2704 return getConstantFP(apf, VT);
2707 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2708 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2709 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2710 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2711 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2712 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2715 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2718 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2721 case ISD::CTLZ_ZERO_UNDEF:
2722 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2725 case ISD::CTTZ_ZERO_UNDEF:
2726 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2731 // Constant fold unary operations with a floating point constant operand.
2732 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2733 APFloat V = C->getValueAPF(); // make copy
2737 return getConstantFP(V, VT);
2740 return getConstantFP(V, VT);
2742 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2743 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2744 return getConstantFP(V, VT);
2748 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2749 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2750 return getConstantFP(V, VT);
2754 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2755 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2756 return getConstantFP(V, VT);
2759 case ISD::FP_EXTEND: {
2761 // This can return overflow, underflow, or inexact; we don't care.
2762 // FIXME need to be more flexible about rounding mode.
2763 (void)V.convert(EVTToAPFloatSemantics(VT),
2764 APFloat::rmNearestTiesToEven, &ignored);
2765 return getConstantFP(V, VT);
2767 case ISD::FP_TO_SINT:
2768 case ISD::FP_TO_UINT: {
2771 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2772 // FIXME need to be more flexible about rounding mode.
2773 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2774 Opcode==ISD::FP_TO_SINT,
2775 APFloat::rmTowardZero, &ignored);
2776 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2778 APInt api(VT.getSizeInBits(), x);
2779 return getConstant(api, VT);
2782 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2783 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2784 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2785 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2786 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2787 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2792 // Constant fold unary operations with a vector integer operand.
2793 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2794 if (BV->isConstant()) {
2797 // FIXME: Entirely reasonable to perform folding of other unary
2798 // operations here as the need arises.
2800 case ISD::UINT_TO_FP:
2801 case ISD::SINT_TO_FP: {
2802 SmallVector<SDValue, 8> Ops;
2803 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2804 SDValue OpN = BV->getOperand(i);
2805 // Let the above scalar folding handle the conversion of each
2807 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2811 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2817 unsigned OpOpcode = Operand.getNode()->getOpcode();
2819 case ISD::TokenFactor:
2820 case ISD::MERGE_VALUES:
2821 case ISD::CONCAT_VECTORS:
2822 return Operand; // Factor, merge or concat of one node? No need.
2823 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2824 case ISD::FP_EXTEND:
2825 assert(VT.isFloatingPoint() &&
2826 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2827 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2828 assert((!VT.isVector() ||
2829 VT.getVectorNumElements() ==
2830 Operand.getValueType().getVectorNumElements()) &&
2831 "Vector element count mismatch!");
2832 if (Operand.getOpcode() == ISD::UNDEF)
2833 return getUNDEF(VT);
2835 case ISD::SIGN_EXTEND:
2836 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2837 "Invalid SIGN_EXTEND!");
2838 if (Operand.getValueType() == VT) return Operand; // noop extension
2839 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2840 "Invalid sext node, dst < src!");
2841 assert((!VT.isVector() ||
2842 VT.getVectorNumElements() ==
2843 Operand.getValueType().getVectorNumElements()) &&
2844 "Vector element count mismatch!");
2845 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2846 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2847 else if (OpOpcode == ISD::UNDEF)
2848 // sext(undef) = 0, because the top bits will all be the same.
2849 return getConstant(0, VT);
2851 case ISD::ZERO_EXTEND:
2852 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2853 "Invalid ZERO_EXTEND!");
2854 if (Operand.getValueType() == VT) return Operand; // noop extension
2855 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2856 "Invalid zext node, dst < src!");
2857 assert((!VT.isVector() ||
2858 VT.getVectorNumElements() ==
2859 Operand.getValueType().getVectorNumElements()) &&
2860 "Vector element count mismatch!");
2861 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2862 return getNode(ISD::ZERO_EXTEND, DL, VT,
2863 Operand.getNode()->getOperand(0));
2864 else if (OpOpcode == ISD::UNDEF)
2865 // zext(undef) = 0, because the top bits will be zero.
2866 return getConstant(0, VT);
2868 case ISD::ANY_EXTEND:
2869 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2870 "Invalid ANY_EXTEND!");
2871 if (Operand.getValueType() == VT) return Operand; // noop extension
2872 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2873 "Invalid anyext node, dst < src!");
2874 assert((!VT.isVector() ||
2875 VT.getVectorNumElements() ==
2876 Operand.getValueType().getVectorNumElements()) &&
2877 "Vector element count mismatch!");
2879 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2880 OpOpcode == ISD::ANY_EXTEND)
2881 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2882 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2883 else if (OpOpcode == ISD::UNDEF)
2884 return getUNDEF(VT);
2886 // (ext (trunx x)) -> x
2887 if (OpOpcode == ISD::TRUNCATE) {
2888 SDValue OpOp = Operand.getNode()->getOperand(0);
2889 if (OpOp.getValueType() == VT)
2894 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2895 "Invalid TRUNCATE!");
2896 if (Operand.getValueType() == VT) return Operand; // noop truncate
2897 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2898 "Invalid truncate node, src < dst!");
2899 assert((!VT.isVector() ||
2900 VT.getVectorNumElements() ==
2901 Operand.getValueType().getVectorNumElements()) &&
2902 "Vector element count mismatch!");
2903 if (OpOpcode == ISD::TRUNCATE)
2904 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2905 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2906 OpOpcode == ISD::ANY_EXTEND) {
2907 // If the source is smaller than the dest, we still need an extend.
2908 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2909 .bitsLT(VT.getScalarType()))
2910 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2911 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2912 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2913 return Operand.getNode()->getOperand(0);
2915 if (OpOpcode == ISD::UNDEF)
2916 return getUNDEF(VT);
2919 // Basic sanity checking.
2920 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2921 && "Cannot BITCAST between types of different sizes!");
2922 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2923 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2924 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2925 if (OpOpcode == ISD::UNDEF)
2926 return getUNDEF(VT);
2928 case ISD::SCALAR_TO_VECTOR:
2929 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2930 (VT.getVectorElementType() == Operand.getValueType() ||
2931 (VT.getVectorElementType().isInteger() &&
2932 Operand.getValueType().isInteger() &&
2933 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2934 "Illegal SCALAR_TO_VECTOR node!");
2935 if (OpOpcode == ISD::UNDEF)
2936 return getUNDEF(VT);
2937 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2938 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2939 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2940 Operand.getConstantOperandVal(1) == 0 &&
2941 Operand.getOperand(0).getValueType() == VT)
2942 return Operand.getOperand(0);
2945 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2946 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2947 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2948 Operand.getNode()->getOperand(0));
2949 if (OpOpcode == ISD::FNEG) // --X -> X
2950 return Operand.getNode()->getOperand(0);
2953 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2954 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2959 SDVTList VTs = getVTList(VT);
2960 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2961 FoldingSetNodeID ID;
2962 SDValue Ops[1] = { Operand };
2963 AddNodeIDNode(ID, Opcode, VTs, Ops);
2965 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2966 return SDValue(E, 0);
2968 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2969 DL.getDebugLoc(), VTs, Operand);
2970 CSEMap.InsertNode(N, IP);
2972 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2973 DL.getDebugLoc(), VTs, Operand);
2977 return SDValue(N, 0);
2980 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2981 SDNode *Cst1, SDNode *Cst2) {
2982 // If the opcode is a target-specific ISD node, there's nothing we can
2983 // do here and the operand rules may not line up with the below, so
2985 if (Opcode >= ISD::BUILTIN_OP_END)
2988 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2989 SmallVector<SDValue, 4> Outputs;
2990 EVT SVT = VT.getScalarType();
2992 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2993 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2994 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2997 if (Scalar1 && Scalar2)
2998 // Scalar instruction.
2999 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3001 // For vectors extract each constant element into Inputs so we can constant
3002 // fold them individually.
3003 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3004 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3008 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3010 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3011 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3012 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3013 if (!V1 || !V2) // Not a constant, bail.
3016 if (V1->isOpaque() || V2->isOpaque())
3019 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3020 // FIXME: This is valid and could be handled by truncating the APInts.
3021 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3024 Inputs.push_back(std::make_pair(V1, V2));
3028 // We have a number of constant values, constant fold them element by element.
3029 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3030 const APInt &C1 = Inputs[I].first->getAPIntValue();
3031 const APInt &C2 = Inputs[I].second->getAPIntValue();
3035 Outputs.push_back(getConstant(C1 + C2, SVT));
3038 Outputs.push_back(getConstant(C1 - C2, SVT));
3041 Outputs.push_back(getConstant(C1 * C2, SVT));
3044 if (!C2.getBoolValue())
3046 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3049 if (!C2.getBoolValue())
3051 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3054 if (!C2.getBoolValue())
3056 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3059 if (!C2.getBoolValue())
3061 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3064 Outputs.push_back(getConstant(C1 & C2, SVT));
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 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3079 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3082 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3085 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3092 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3093 "Expected a scalar or vector!"));
3095 // Handle the scalar case first.
3097 return Outputs.back();
3099 // We may have a vector type but a scalar result. Create a splat.
3100 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3102 // Build a big vector out of the scalar elements we generated.
3103 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3106 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3107 SDValue N2, bool nuw, bool nsw, bool exact) {
3108 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3109 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3112 case ISD::TokenFactor:
3113 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3114 N2.getValueType() == MVT::Other && "Invalid token factor!");
3115 // Fold trivial token factors.
3116 if (N1.getOpcode() == ISD::EntryToken) return N2;
3117 if (N2.getOpcode() == ISD::EntryToken) return N1;
3118 if (N1 == N2) return N1;
3120 case ISD::CONCAT_VECTORS:
3121 // Concat of UNDEFs is UNDEF.
3122 if (N1.getOpcode() == ISD::UNDEF &&
3123 N2.getOpcode() == ISD::UNDEF)
3124 return getUNDEF(VT);
3126 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3127 // one big BUILD_VECTOR.
3128 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3129 N2.getOpcode() == ISD::BUILD_VECTOR) {
3130 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3131 N1.getNode()->op_end());
3132 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3133 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3137 assert(VT.isInteger() && "This operator does not apply to FP types!");
3138 assert(N1.getValueType() == N2.getValueType() &&
3139 N1.getValueType() == VT && "Binary operator types must match!");
3140 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3141 // worth handling here.
3142 if (N2C && N2C->isNullValue())
3144 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3151 assert(VT.isInteger() && "This operator does not apply to FP types!");
3152 assert(N1.getValueType() == N2.getValueType() &&
3153 N1.getValueType() == VT && "Binary operator types must match!");
3154 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3155 // it's worth handling here.
3156 if (N2C && N2C->isNullValue())
3166 assert(VT.isInteger() && "This operator does not apply to FP types!");
3167 assert(N1.getValueType() == N2.getValueType() &&
3168 N1.getValueType() == VT && "Binary operator types must match!");
3175 if (getTarget().Options.UnsafeFPMath) {
3176 if (Opcode == ISD::FADD) {
3178 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3179 if (CFP->getValueAPF().isZero())
3182 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3183 if (CFP->getValueAPF().isZero())
3185 } else if (Opcode == ISD::FSUB) {
3187 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3188 if (CFP->getValueAPF().isZero())
3190 } else if (Opcode == ISD::FMUL) {
3191 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3194 // If the first operand isn't the constant, try the second
3196 CFP = dyn_cast<ConstantFPSDNode>(N2);
3203 return SDValue(CFP,0);
3205 if (CFP->isExactlyValue(1.0))
3210 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3211 assert(N1.getValueType() == N2.getValueType() &&
3212 N1.getValueType() == VT && "Binary operator types must match!");
3214 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3215 assert(N1.getValueType() == VT &&
3216 N1.getValueType().isFloatingPoint() &&
3217 N2.getValueType().isFloatingPoint() &&
3218 "Invalid FCOPYSIGN!");
3225 assert(VT == N1.getValueType() &&
3226 "Shift operators return type must be the same as their first arg");
3227 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3228 "Shifts only work on integers");
3229 assert((!VT.isVector() || VT == N2.getValueType()) &&
3230 "Vector shift amounts must be in the same as their first arg");
3231 // Verify that the shift amount VT is bit enough to hold valid shift
3232 // amounts. This catches things like trying to shift an i1024 value by an
3233 // i8, which is easy to fall into in generic code that uses
3234 // TLI.getShiftAmount().
3235 assert(N2.getValueType().getSizeInBits() >=
3236 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3237 "Invalid use of small shift amount with oversized value!");
3239 // Always fold shifts of i1 values so the code generator doesn't need to
3240 // handle them. Since we know the size of the shift has to be less than the
3241 // size of the value, the shift/rotate count is guaranteed to be zero.
3244 if (N2C && N2C->isNullValue())
3247 case ISD::FP_ROUND_INREG: {
3248 EVT EVT = cast<VTSDNode>(N2)->getVT();
3249 assert(VT == N1.getValueType() && "Not an inreg round!");
3250 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3251 "Cannot FP_ROUND_INREG integer types");
3252 assert(EVT.isVector() == VT.isVector() &&
3253 "FP_ROUND_INREG type should be vector iff the operand "
3255 assert((!EVT.isVector() ||
3256 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3257 "Vector element counts must match in FP_ROUND_INREG");
3258 assert(EVT.bitsLE(VT) && "Not rounding down!");
3260 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3264 assert(VT.isFloatingPoint() &&
3265 N1.getValueType().isFloatingPoint() &&
3266 VT.bitsLE(N1.getValueType()) &&
3267 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3268 if (N1.getValueType() == VT) return N1; // noop conversion.
3270 case ISD::AssertSext:
3271 case ISD::AssertZext: {
3272 EVT EVT = cast<VTSDNode>(N2)->getVT();
3273 assert(VT == N1.getValueType() && "Not an inreg extend!");
3274 assert(VT.isInteger() && EVT.isInteger() &&
3275 "Cannot *_EXTEND_INREG FP types");
3276 assert(!EVT.isVector() &&
3277 "AssertSExt/AssertZExt type should be the vector element type "
3278 "rather than the vector type!");
3279 assert(EVT.bitsLE(VT) && "Not extending!");
3280 if (VT == EVT) return N1; // noop assertion.
3283 case ISD::SIGN_EXTEND_INREG: {
3284 EVT EVT = cast<VTSDNode>(N2)->getVT();
3285 assert(VT == N1.getValueType() && "Not an inreg extend!");
3286 assert(VT.isInteger() && EVT.isInteger() &&
3287 "Cannot *_EXTEND_INREG FP types");
3288 assert(EVT.isVector() == VT.isVector() &&
3289 "SIGN_EXTEND_INREG type should be vector iff the operand "
3291 assert((!EVT.isVector() ||
3292 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3293 "Vector element counts must match in SIGN_EXTEND_INREG");
3294 assert(EVT.bitsLE(VT) && "Not extending!");
3295 if (EVT == VT) return N1; // Not actually extending
3298 APInt Val = N1C->getAPIntValue();
3299 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3300 Val <<= Val.getBitWidth()-FromBits;
3301 Val = Val.ashr(Val.getBitWidth()-FromBits);
3302 return getConstant(Val, VT);
3306 case ISD::EXTRACT_VECTOR_ELT:
3307 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3308 if (N1.getOpcode() == ISD::UNDEF)
3309 return getUNDEF(VT);
3311 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3312 // expanding copies of large vectors from registers.
3314 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3315 N1.getNumOperands() > 0) {
3317 N1.getOperand(0).getValueType().getVectorNumElements();
3318 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3319 N1.getOperand(N2C->getZExtValue() / Factor),
3320 getConstant(N2C->getZExtValue() % Factor,
3321 N2.getValueType()));
3324 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3325 // expanding large vector constants.
3326 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3327 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3329 if (VT != Elt.getValueType())
3330 // If the vector element type is not legal, the BUILD_VECTOR operands
3331 // are promoted and implicitly truncated, and the result implicitly
3332 // extended. Make that explicit here.
3333 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3338 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3339 // operations are lowered to scalars.
3340 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3341 // If the indices are the same, return the inserted element else
3342 // if the indices are known different, extract the element from
3343 // the original vector.
3344 SDValue N1Op2 = N1.getOperand(2);
3345 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3347 if (N1Op2C && N2C) {
3348 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3349 if (VT == N1.getOperand(1).getValueType())
3350 return N1.getOperand(1);
3352 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3355 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3359 case ISD::EXTRACT_ELEMENT:
3360 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3361 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3362 (N1.getValueType().isInteger() == VT.isInteger()) &&
3363 N1.getValueType() != VT &&
3364 "Wrong types for EXTRACT_ELEMENT!");
3366 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3367 // 64-bit integers into 32-bit parts. Instead of building the extract of
3368 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3369 if (N1.getOpcode() == ISD::BUILD_PAIR)
3370 return N1.getOperand(N2C->getZExtValue());
3372 // EXTRACT_ELEMENT of a constant int is also very common.
3373 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3374 unsigned ElementSize = VT.getSizeInBits();
3375 unsigned Shift = ElementSize * N2C->getZExtValue();
3376 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3377 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3380 case ISD::EXTRACT_SUBVECTOR: {
3382 if (VT.isSimple() && N1.getValueType().isSimple()) {
3383 assert(VT.isVector() && N1.getValueType().isVector() &&
3384 "Extract subvector VTs must be a vectors!");
3385 assert(VT.getVectorElementType() ==
3386 N1.getValueType().getVectorElementType() &&
3387 "Extract subvector VTs must have the same element type!");
3388 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3389 "Extract subvector must be from larger vector to smaller vector!");
3391 if (isa<ConstantSDNode>(Index.getNode())) {
3392 assert((VT.getVectorNumElements() +
3393 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3394 <= N1.getValueType().getVectorNumElements())
3395 && "Extract subvector overflow!");
3398 // Trivial extraction.
3399 if (VT.getSimpleVT() == N1.getSimpleValueType())
3406 // Perform trivial constant folding.
3408 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3411 // Canonicalize constant to RHS if commutative.
3412 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3413 std::swap(N1C, N2C);
3417 // Constant fold FP operations.
3418 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3419 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3420 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3422 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3423 // Canonicalize constant to RHS if commutative.
3424 std::swap(N1CFP, N2CFP);
3427 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3428 APFloat::opStatus s;
3431 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3432 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3433 return getConstantFP(V1, VT);
3436 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3437 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3438 return getConstantFP(V1, VT);
3441 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3442 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3443 return getConstantFP(V1, VT);
3446 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3447 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3448 s!=APFloat::opDivByZero)) {
3449 return getConstantFP(V1, VT);
3453 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3454 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3455 s!=APFloat::opDivByZero)) {
3456 return getConstantFP(V1, VT);
3459 case ISD::FCOPYSIGN:
3461 return getConstantFP(V1, VT);
3466 if (Opcode == ISD::FP_ROUND) {
3467 APFloat V = N1CFP->getValueAPF(); // make copy
3469 // This can return overflow, underflow, or inexact; we don't care.
3470 // FIXME need to be more flexible about rounding mode.
3471 (void)V.convert(EVTToAPFloatSemantics(VT),
3472 APFloat::rmNearestTiesToEven, &ignored);
3473 return getConstantFP(V, VT);
3477 // Canonicalize an UNDEF to the RHS, even over a constant.
3478 if (N1.getOpcode() == ISD::UNDEF) {
3479 if (isCommutativeBinOp(Opcode)) {
3483 case ISD::FP_ROUND_INREG:
3484 case ISD::SIGN_EXTEND_INREG:
3490 return N1; // fold op(undef, arg2) -> undef
3498 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3499 // For vectors, we can't easily build an all zero vector, just return
3506 // Fold a bunch of operators when the RHS is undef.
3507 if (N2.getOpcode() == ISD::UNDEF) {
3510 if (N1.getOpcode() == ISD::UNDEF)
3511 // Handle undef ^ undef -> 0 special case. This is a common
3513 return getConstant(0, VT);
3523 return N2; // fold op(arg1, undef) -> undef
3529 if (getTarget().Options.UnsafeFPMath)
3537 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3538 // For vectors, we can't easily build an all zero vector, just return
3543 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3544 // For vectors, we can't easily build an all one vector, just return
3552 // Memoize this node if possible.
3554 SDVTList VTs = getVTList(VT);
3555 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3556 if (VT != MVT::Glue) {
3557 SDValue Ops[] = {N1, N2};
3558 FoldingSetNodeID ID;
3559 AddNodeIDNode(ID, Opcode, VTs, Ops);
3561 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3563 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3564 return SDValue(E, 0);
3566 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3568 CSEMap.InsertNode(N, IP);
3571 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3575 return SDValue(N, 0);
3578 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3579 SDValue N1, SDValue N2, SDValue N3) {
3580 // Perform various simplifications.
3581 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3584 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3585 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3586 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3587 if (N1CFP && N2CFP && N3CFP) {
3588 APFloat V1 = N1CFP->getValueAPF();
3589 const APFloat &V2 = N2CFP->getValueAPF();
3590 const APFloat &V3 = N3CFP->getValueAPF();
3591 APFloat::opStatus s =
3592 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3593 if (s != APFloat::opInvalidOp)
3594 return getConstantFP(V1, VT);
3598 case ISD::CONCAT_VECTORS:
3599 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3600 // one big BUILD_VECTOR.
3601 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3602 N2.getOpcode() == ISD::BUILD_VECTOR &&
3603 N3.getOpcode() == ISD::BUILD_VECTOR) {
3604 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3605 N1.getNode()->op_end());
3606 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3607 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3608 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3612 // Use FoldSetCC to simplify SETCC's.
3613 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3614 if (Simp.getNode()) return Simp;
3619 if (N1C->getZExtValue())
3620 return N2; // select true, X, Y -> X
3621 return N3; // select false, X, Y -> Y
3624 if (N2 == N3) return N2; // select C, X, X -> X
3626 case ISD::VECTOR_SHUFFLE:
3627 llvm_unreachable("should use getVectorShuffle constructor!");
3628 case ISD::INSERT_SUBVECTOR: {
3630 if (VT.isSimple() && N1.getValueType().isSimple()
3631 && N2.getValueType().isSimple()) {
3632 assert(VT.isVector() && N1.getValueType().isVector() &&
3633 N2.getValueType().isVector() &&
3634 "Insert subvector VTs must be a vectors");
3635 assert(VT == N1.getValueType() &&
3636 "Dest and insert subvector source types must match!");
3637 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3638 "Insert subvector must be from smaller vector to larger vector!");
3639 if (isa<ConstantSDNode>(Index.getNode())) {
3640 assert((N2.getValueType().getVectorNumElements() +
3641 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3642 <= VT.getVectorNumElements())
3643 && "Insert subvector overflow!");
3646 // Trivial insertion.
3647 if (VT.getSimpleVT() == N2.getSimpleValueType())
3653 // Fold bit_convert nodes from a type to themselves.
3654 if (N1.getValueType() == VT)
3659 // Memoize node if it doesn't produce a flag.
3661 SDVTList VTs = getVTList(VT);
3662 if (VT != MVT::Glue) {
3663 SDValue Ops[] = { N1, N2, N3 };
3664 FoldingSetNodeID ID;
3665 AddNodeIDNode(ID, Opcode, VTs, Ops);
3667 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3668 return SDValue(E, 0);
3670 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3671 DL.getDebugLoc(), VTs, N1, N2, N3);
3672 CSEMap.InsertNode(N, IP);
3674 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3675 DL.getDebugLoc(), VTs, N1, N2, N3);
3679 return SDValue(N, 0);
3682 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3683 SDValue N1, SDValue N2, SDValue N3,
3685 SDValue Ops[] = { N1, N2, N3, N4 };
3686 return getNode(Opcode, DL, VT, Ops);
3689 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3690 SDValue N1, SDValue N2, SDValue N3,
3691 SDValue N4, SDValue N5) {
3692 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3693 return getNode(Opcode, DL, VT, Ops);
3696 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3697 /// the incoming stack arguments to be loaded from the stack.
3698 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3699 SmallVector<SDValue, 8> ArgChains;
3701 // Include the original chain at the beginning of the list. When this is
3702 // used by target LowerCall hooks, this helps legalize find the
3703 // CALLSEQ_BEGIN node.
3704 ArgChains.push_back(Chain);
3706 // Add a chain value for each stack argument.
3707 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3708 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3709 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3710 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3711 if (FI->getIndex() < 0)
3712 ArgChains.push_back(SDValue(L, 1));
3714 // Build a tokenfactor for all the chains.
3715 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3718 /// getMemsetValue - Vectorized representation of the memset value
3720 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3722 assert(Value.getOpcode() != ISD::UNDEF);
3724 unsigned NumBits = VT.getScalarType().getSizeInBits();
3725 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3726 assert(C->getAPIntValue().getBitWidth() == 8);
3727 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3729 return DAG.getConstant(Val, VT);
3730 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3733 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3735 // Use a multiplication with 0x010101... to extend the input to the
3737 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3738 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3744 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3745 /// used when a memcpy is turned into a memset when the source is a constant
3747 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3748 const TargetLowering &TLI, StringRef Str) {
3749 // Handle vector with all elements zero.
3752 return DAG.getConstant(0, VT);
3753 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3754 return DAG.getConstantFP(0.0, VT);
3755 else if (VT.isVector()) {
3756 unsigned NumElts = VT.getVectorNumElements();
3757 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3758 return DAG.getNode(ISD::BITCAST, dl, VT,
3759 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3762 llvm_unreachable("Expected type!");
3765 assert(!VT.isVector() && "Can't handle vector type here!");
3766 unsigned NumVTBits = VT.getSizeInBits();
3767 unsigned NumVTBytes = NumVTBits / 8;
3768 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3770 APInt Val(NumVTBits, 0);
3771 if (TLI.isLittleEndian()) {
3772 for (unsigned i = 0; i != NumBytes; ++i)
3773 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3775 for (unsigned i = 0; i != NumBytes; ++i)
3776 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3779 // If the "cost" of materializing the integer immediate is less than the cost
3780 // of a load, then it is cost effective to turn the load into the immediate.
3781 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3782 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3783 return DAG.getConstant(Val, VT);
3784 return SDValue(nullptr, 0);
3787 /// getMemBasePlusOffset - Returns base and offset node for the
3789 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3790 SelectionDAG &DAG) {
3791 EVT VT = Base.getValueType();
3792 return DAG.getNode(ISD::ADD, dl,
3793 VT, Base, DAG.getConstant(Offset, VT));
3796 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3798 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3799 unsigned SrcDelta = 0;
3800 GlobalAddressSDNode *G = nullptr;
3801 if (Src.getOpcode() == ISD::GlobalAddress)
3802 G = cast<GlobalAddressSDNode>(Src);
3803 else if (Src.getOpcode() == ISD::ADD &&
3804 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3805 Src.getOperand(1).getOpcode() == ISD::Constant) {
3806 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3807 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3812 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3815 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3816 /// to replace the memset / memcpy. Return true if the number of memory ops
3817 /// is below the threshold. It returns the types of the sequence of
3818 /// memory ops to perform memset / memcpy by reference.
3819 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3820 unsigned Limit, uint64_t Size,
3821 unsigned DstAlign, unsigned SrcAlign,
3827 const TargetLowering &TLI) {
3828 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3829 "Expecting memcpy / memset source to meet alignment requirement!");
3830 // If 'SrcAlign' is zero, that means the memory operation does not need to
3831 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3832 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3833 // is the specified alignment of the memory operation. If it is zero, that
3834 // means it's possible to change the alignment of the destination.
3835 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3836 // not need to be loaded.
3837 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3838 IsMemset, ZeroMemset, MemcpyStrSrc,
3839 DAG.getMachineFunction());
3841 if (VT == MVT::Other) {
3843 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3844 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3845 VT = TLI.getPointerTy();
3847 switch (DstAlign & 7) {
3848 case 0: VT = MVT::i64; break;
3849 case 4: VT = MVT::i32; break;
3850 case 2: VT = MVT::i16; break;
3851 default: VT = MVT::i8; break;
3856 while (!TLI.isTypeLegal(LVT))
3857 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3858 assert(LVT.isInteger());
3864 unsigned NumMemOps = 0;
3866 unsigned VTSize = VT.getSizeInBits() / 8;
3867 while (VTSize > Size) {
3868 // For now, only use non-vector load / store's for the left-over pieces.
3873 if (VT.isVector() || VT.isFloatingPoint()) {
3874 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3875 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3876 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3878 else if (NewVT == MVT::i64 &&
3879 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3880 TLI.isSafeMemOpType(MVT::f64)) {
3881 // i64 is usually not legal on 32-bit targets, but f64 may be.
3889 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3890 if (NewVT == MVT::i8)
3892 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3894 NewVTSize = NewVT.getSizeInBits() / 8;
3896 // If the new VT cannot cover all of the remaining bits, then consider
3897 // issuing a (or a pair of) unaligned and overlapping load / store.
3898 // FIXME: Only does this for 64-bit or more since we don't have proper
3899 // cost model for unaligned load / store.
3902 if (NumMemOps && AllowOverlap &&
3903 VTSize >= 8 && NewVTSize < Size &&
3904 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3912 if (++NumMemOps > Limit)
3915 MemOps.push_back(VT);
3922 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3923 SDValue Chain, SDValue Dst,
3924 SDValue Src, uint64_t Size,
3925 unsigned Align, bool isVol,
3927 MachinePointerInfo DstPtrInfo,
3928 MachinePointerInfo SrcPtrInfo) {
3929 // Turn a memcpy of undef to nop.
3930 if (Src.getOpcode() == ISD::UNDEF)
3933 // Expand memcpy to a series of load and store ops if the size operand falls
3934 // below a certain threshold.
3935 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3936 // rather than maybe a humongous number of loads and stores.
3937 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3938 std::vector<EVT> MemOps;
3939 bool DstAlignCanChange = false;
3940 MachineFunction &MF = DAG.getMachineFunction();
3941 MachineFrameInfo *MFI = MF.getFrameInfo();
3943 MF.getFunction()->getAttributes().
3944 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3945 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3946 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3947 DstAlignCanChange = true;
3948 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3949 if (Align > SrcAlign)
3952 bool CopyFromStr = isMemSrcFromString(Src, Str);
3953 bool isZeroStr = CopyFromStr && Str.empty();
3954 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3956 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3957 (DstAlignCanChange ? 0 : Align),
3958 (isZeroStr ? 0 : SrcAlign),
3959 false, false, CopyFromStr, true, DAG, TLI))
3962 if (DstAlignCanChange) {
3963 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3964 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3966 // Don't promote to an alignment that would require dynamic stack
3968 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3969 if (!TRI->needsStackRealignment(MF))
3970 while (NewAlign > Align &&
3971 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3974 if (NewAlign > Align) {
3975 // Give the stack frame object a larger alignment if needed.
3976 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3977 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3982 SmallVector<SDValue, 8> OutChains;
3983 unsigned NumMemOps = MemOps.size();
3984 uint64_t SrcOff = 0, DstOff = 0;
3985 for (unsigned i = 0; i != NumMemOps; ++i) {
3987 unsigned VTSize = VT.getSizeInBits() / 8;
3988 SDValue Value, Store;
3990 if (VTSize > Size) {
3991 // Issuing an unaligned load / store pair that overlaps with the previous
3992 // pair. Adjust the offset accordingly.
3993 assert(i == NumMemOps-1 && i != 0);
3994 SrcOff -= VTSize - Size;
3995 DstOff -= VTSize - Size;
3999 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4000 // It's unlikely a store of a vector immediate can be done in a single
4001 // instruction. It would require a load from a constantpool first.
4002 // We only handle zero vectors here.
4003 // FIXME: Handle other cases where store of vector immediate is done in
4004 // a single instruction.
4005 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4006 if (Value.getNode())
4007 Store = DAG.getStore(Chain, dl, Value,
4008 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4009 DstPtrInfo.getWithOffset(DstOff), isVol,
4013 if (!Store.getNode()) {
4014 // The type might not be legal for the target. This should only happen
4015 // if the type is smaller than a legal type, as on PPC, so the right
4016 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4017 // to Load/Store if NVT==VT.
4018 // FIXME does the case above also need this?
4019 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4020 assert(NVT.bitsGE(VT));
4021 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4022 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4023 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4024 false, MinAlign(SrcAlign, SrcOff));
4025 Store = DAG.getTruncStore(Chain, dl, Value,
4026 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4027 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4030 OutChains.push_back(Store);
4036 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4039 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4040 SDValue Chain, SDValue Dst,
4041 SDValue Src, uint64_t Size,
4042 unsigned Align, bool isVol,
4044 MachinePointerInfo DstPtrInfo,
4045 MachinePointerInfo SrcPtrInfo) {
4046 // Turn a memmove of undef to nop.
4047 if (Src.getOpcode() == ISD::UNDEF)
4050 // Expand memmove to a series of load and store ops if the size operand falls
4051 // below a certain threshold.
4052 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4053 std::vector<EVT> MemOps;
4054 bool DstAlignCanChange = false;
4055 MachineFunction &MF = DAG.getMachineFunction();
4056 MachineFrameInfo *MFI = MF.getFrameInfo();
4057 bool OptSize = MF.getFunction()->getAttributes().
4058 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4059 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4060 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4061 DstAlignCanChange = true;
4062 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4063 if (Align > SrcAlign)
4065 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4067 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4068 (DstAlignCanChange ? 0 : Align), SrcAlign,
4069 false, false, false, false, DAG, TLI))
4072 if (DstAlignCanChange) {
4073 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4074 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4075 if (NewAlign > Align) {
4076 // Give the stack frame object a larger alignment if needed.
4077 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4078 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4083 uint64_t SrcOff = 0, DstOff = 0;
4084 SmallVector<SDValue, 8> LoadValues;
4085 SmallVector<SDValue, 8> LoadChains;
4086 SmallVector<SDValue, 8> OutChains;
4087 unsigned NumMemOps = MemOps.size();
4088 for (unsigned i = 0; i < NumMemOps; i++) {
4090 unsigned VTSize = VT.getSizeInBits() / 8;
4093 Value = DAG.getLoad(VT, dl, Chain,
4094 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4095 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4096 false, false, SrcAlign);
4097 LoadValues.push_back(Value);
4098 LoadChains.push_back(Value.getValue(1));
4101 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4103 for (unsigned i = 0; i < NumMemOps; i++) {
4105 unsigned VTSize = VT.getSizeInBits() / 8;
4108 Store = DAG.getStore(Chain, dl, LoadValues[i],
4109 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4110 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4111 OutChains.push_back(Store);
4115 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4118 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4121 /// \param DAG Selection DAG where lowered code is placed.
4122 /// \param dl Link to corresponding IR location.
4123 /// \param Chain Control flow dependency.
4124 /// \param Dst Pointer to destination memory location.
4125 /// \param Src Value of byte to write into the memory.
4126 /// \param Size Number of bytes to write.
4127 /// \param Align Alignment of the destination in bytes.
4128 /// \param isVol True if destination is volatile.
4129 /// \param DstPtrInfo IR information on the memory pointer.
4130 /// \returns New head in the control flow, if lowering was successful, empty
4131 /// SDValue otherwise.
4133 /// The function tries to replace 'llvm.memset' intrinsic with several store
4134 /// operations and value calculation code. This is usually profitable for small
4136 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4137 SDValue Chain, SDValue Dst,
4138 SDValue Src, uint64_t Size,
4139 unsigned Align, bool isVol,
4140 MachinePointerInfo DstPtrInfo) {
4141 // Turn a memset of undef to nop.
4142 if (Src.getOpcode() == ISD::UNDEF)
4145 // Expand memset to a series of load/store ops if the size operand
4146 // falls below a certain threshold.
4147 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4148 std::vector<EVT> MemOps;
4149 bool DstAlignCanChange = false;
4150 MachineFunction &MF = DAG.getMachineFunction();
4151 MachineFrameInfo *MFI = MF.getFrameInfo();
4152 bool OptSize = MF.getFunction()->getAttributes().
4153 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4154 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4155 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4156 DstAlignCanChange = true;
4158 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4159 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4160 Size, (DstAlignCanChange ? 0 : Align), 0,
4161 true, IsZeroVal, false, true, DAG, TLI))
4164 if (DstAlignCanChange) {
4165 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4166 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4167 if (NewAlign > Align) {
4168 // Give the stack frame object a larger alignment if needed.
4169 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4170 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4175 SmallVector<SDValue, 8> OutChains;
4176 uint64_t DstOff = 0;
4177 unsigned NumMemOps = MemOps.size();
4179 // Find the largest store and generate the bit pattern for it.
4180 EVT LargestVT = MemOps[0];
4181 for (unsigned i = 1; i < NumMemOps; i++)
4182 if (MemOps[i].bitsGT(LargestVT))
4183 LargestVT = MemOps[i];
4184 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4186 for (unsigned i = 0; i < NumMemOps; i++) {
4188 unsigned VTSize = VT.getSizeInBits() / 8;
4189 if (VTSize > Size) {
4190 // Issuing an unaligned load / store pair that overlaps with the previous
4191 // pair. Adjust the offset accordingly.
4192 assert(i == NumMemOps-1 && i != 0);
4193 DstOff -= VTSize - Size;
4196 // If this store is smaller than the largest store see whether we can get
4197 // the smaller value for free with a truncate.
4198 SDValue Value = MemSetValue;
4199 if (VT.bitsLT(LargestVT)) {
4200 if (!LargestVT.isVector() && !VT.isVector() &&
4201 TLI.isTruncateFree(LargestVT, VT))
4202 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4204 Value = getMemsetValue(Src, VT, DAG, dl);
4206 assert(Value.getValueType() == VT && "Value with wrong type.");
4207 SDValue Store = DAG.getStore(Chain, dl, Value,
4208 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4209 DstPtrInfo.getWithOffset(DstOff),
4210 isVol, false, Align);
4211 OutChains.push_back(Store);
4212 DstOff += VT.getSizeInBits() / 8;
4216 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4219 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4220 SDValue Src, SDValue Size,
4221 unsigned Align, bool isVol, bool AlwaysInline,
4222 MachinePointerInfo DstPtrInfo,
4223 MachinePointerInfo SrcPtrInfo) {
4224 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4226 // Check to see if we should lower the memcpy to loads and stores first.
4227 // For cases within the target-specified limits, this is the best choice.
4228 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4230 // Memcpy with size zero? Just return the original chain.
4231 if (ConstantSize->isNullValue())
4234 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4235 ConstantSize->getZExtValue(),Align,
4236 isVol, false, DstPtrInfo, SrcPtrInfo);
4237 if (Result.getNode())
4241 // Then check to see if we should lower the memcpy with target-specific
4242 // code. If the target chooses to do this, this is the next best.
4244 TSI->EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4245 isVol, AlwaysInline, DstPtrInfo, SrcPtrInfo);
4246 if (Result.getNode())
4249 // If we really need inline code and the target declined to provide it,
4250 // use a (potentially long) sequence of loads and stores.
4252 assert(ConstantSize && "AlwaysInline requires a constant size!");
4253 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4254 ConstantSize->getZExtValue(), Align, isVol,
4255 true, DstPtrInfo, SrcPtrInfo);
4258 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4259 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4260 // respect volatile, so they may do things like read or write memory
4261 // beyond the given memory regions. But fixing this isn't easy, and most
4262 // people don't care.
4264 // Emit a library call.
4265 TargetLowering::ArgListTy Args;
4266 TargetLowering::ArgListEntry Entry;
4267 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4268 Entry.Node = Dst; Args.push_back(Entry);
4269 Entry.Node = Src; Args.push_back(Entry);
4270 Entry.Node = Size; Args.push_back(Entry);
4271 // FIXME: pass in SDLoc
4272 TargetLowering::CallLoweringInfo CLI(*this);
4273 CLI.setDebugLoc(dl).setChain(Chain)
4274 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4275 Type::getVoidTy(*getContext()),
4276 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4277 TLI->getPointerTy()), std::move(Args), 0)
4278 .setDiscardResult();
4279 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4281 return CallResult.second;
4284 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4285 SDValue Src, SDValue Size,
4286 unsigned Align, bool isVol,
4287 MachinePointerInfo DstPtrInfo,
4288 MachinePointerInfo SrcPtrInfo) {
4289 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4291 // Check to see if we should lower the memmove to loads and stores first.
4292 // For cases within the target-specified limits, this is the best choice.
4293 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4295 // Memmove with size zero? Just return the original chain.
4296 if (ConstantSize->isNullValue())
4300 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4301 ConstantSize->getZExtValue(), Align, isVol,
4302 false, DstPtrInfo, SrcPtrInfo);
4303 if (Result.getNode())
4307 // Then check to see if we should lower the memmove with target-specific
4308 // code. If the target chooses to do this, this is the next best.
4309 SDValue Result = TSI->EmitTargetCodeForMemmove(
4310 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4311 if (Result.getNode())
4314 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4315 // not be safe. See memcpy above for more details.
4317 // Emit a library call.
4318 TargetLowering::ArgListTy Args;
4319 TargetLowering::ArgListEntry Entry;
4320 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4321 Entry.Node = Dst; Args.push_back(Entry);
4322 Entry.Node = Src; Args.push_back(Entry);
4323 Entry.Node = Size; Args.push_back(Entry);
4324 // FIXME: pass in SDLoc
4325 TargetLowering::CallLoweringInfo CLI(*this);
4326 CLI.setDebugLoc(dl).setChain(Chain)
4327 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4328 Type::getVoidTy(*getContext()),
4329 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4330 TLI->getPointerTy()), std::move(Args), 0)
4331 .setDiscardResult();
4332 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4334 return CallResult.second;
4337 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4338 SDValue Src, SDValue Size,
4339 unsigned Align, bool isVol,
4340 MachinePointerInfo DstPtrInfo) {
4341 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4343 // Check to see if we should lower the memset to stores first.
4344 // For cases within the target-specified limits, this is the best choice.
4345 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4347 // Memset with size zero? Just return the original chain.
4348 if (ConstantSize->isNullValue())
4352 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4353 Align, isVol, DstPtrInfo);
4355 if (Result.getNode())
4359 // Then check to see if we should lower the memset with target-specific
4360 // code. If the target chooses to do this, this is the next best.
4361 SDValue Result = TSI->EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src,
4362 Size, Align, isVol, DstPtrInfo);
4363 if (Result.getNode())
4366 // Emit a library call.
4367 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4368 TargetLowering::ArgListTy Args;
4369 TargetLowering::ArgListEntry Entry;
4370 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4371 Args.push_back(Entry);
4373 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4374 Args.push_back(Entry);
4376 Entry.Ty = IntPtrTy;
4377 Args.push_back(Entry);
4379 // FIXME: pass in SDLoc
4380 TargetLowering::CallLoweringInfo CLI(*this);
4381 CLI.setDebugLoc(dl).setChain(Chain)
4382 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4383 Type::getVoidTy(*getContext()),
4384 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4385 TLI->getPointerTy()), std::move(Args), 0)
4386 .setDiscardResult();
4388 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4389 return CallResult.second;
4392 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4393 SDVTList VTList, ArrayRef<SDValue> Ops,
4394 MachineMemOperand *MMO,
4395 AtomicOrdering SuccessOrdering,
4396 AtomicOrdering FailureOrdering,
4397 SynchronizationScope SynchScope) {
4398 FoldingSetNodeID ID;
4399 ID.AddInteger(MemVT.getRawBits());
4400 AddNodeIDNode(ID, Opcode, VTList, Ops);
4401 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4403 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4404 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4405 return SDValue(E, 0);
4408 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4409 // SDNode doesn't have access to it. This memory will be "leaked" when
4410 // the node is deallocated, but recovered when the allocator is released.
4411 // If the number of operands is less than 5 we use AtomicSDNode's internal
4413 unsigned NumOps = Ops.size();
4414 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4417 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4418 dl.getDebugLoc(), VTList, MemVT,
4419 Ops.data(), DynOps, NumOps, MMO,
4420 SuccessOrdering, FailureOrdering,
4422 CSEMap.InsertNode(N, IP);
4424 return SDValue(N, 0);
4427 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4428 SDVTList VTList, ArrayRef<SDValue> Ops,
4429 MachineMemOperand *MMO,
4430 AtomicOrdering Ordering,
4431 SynchronizationScope SynchScope) {
4432 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4433 Ordering, SynchScope);
4436 SDValue SelectionDAG::getAtomicCmpSwap(
4437 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4438 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4439 unsigned Alignment, AtomicOrdering SuccessOrdering,
4440 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4441 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4442 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4443 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4445 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4446 Alignment = getEVTAlignment(MemVT);
4448 MachineFunction &MF = getMachineFunction();
4450 // FIXME: Volatile isn't really correct; we should keep track of atomic
4451 // orderings in the memoperand.
4452 unsigned Flags = MachineMemOperand::MOVolatile;
4453 Flags |= MachineMemOperand::MOLoad;
4454 Flags |= MachineMemOperand::MOStore;
4456 MachineMemOperand *MMO =
4457 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4459 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4460 SuccessOrdering, FailureOrdering, SynchScope);
4463 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4464 SDVTList VTs, SDValue Chain, SDValue Ptr,
4465 SDValue Cmp, SDValue Swp,
4466 MachineMemOperand *MMO,
4467 AtomicOrdering SuccessOrdering,
4468 AtomicOrdering FailureOrdering,
4469 SynchronizationScope SynchScope) {
4470 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4471 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4472 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4474 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4475 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4476 SuccessOrdering, FailureOrdering, SynchScope);
4479 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4481 SDValue Ptr, SDValue Val,
4482 const Value* PtrVal,
4484 AtomicOrdering Ordering,
4485 SynchronizationScope SynchScope) {
4486 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4487 Alignment = getEVTAlignment(MemVT);
4489 MachineFunction &MF = getMachineFunction();
4490 // An atomic store does not load. An atomic load does not store.
4491 // (An atomicrmw obviously both loads and stores.)
4492 // For now, atomics are considered to be volatile always, and they are
4494 // FIXME: Volatile isn't really correct; we should keep track of atomic
4495 // orderings in the memoperand.
4496 unsigned Flags = MachineMemOperand::MOVolatile;
4497 if (Opcode != ISD::ATOMIC_STORE)
4498 Flags |= MachineMemOperand::MOLoad;
4499 if (Opcode != ISD::ATOMIC_LOAD)
4500 Flags |= MachineMemOperand::MOStore;
4502 MachineMemOperand *MMO =
4503 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4504 MemVT.getStoreSize(), Alignment);
4506 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4507 Ordering, SynchScope);
4510 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4512 SDValue Ptr, SDValue Val,
4513 MachineMemOperand *MMO,
4514 AtomicOrdering Ordering,
4515 SynchronizationScope SynchScope) {
4516 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4517 Opcode == ISD::ATOMIC_LOAD_SUB ||
4518 Opcode == ISD::ATOMIC_LOAD_AND ||
4519 Opcode == ISD::ATOMIC_LOAD_OR ||
4520 Opcode == ISD::ATOMIC_LOAD_XOR ||
4521 Opcode == ISD::ATOMIC_LOAD_NAND ||
4522 Opcode == ISD::ATOMIC_LOAD_MIN ||
4523 Opcode == ISD::ATOMIC_LOAD_MAX ||
4524 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4525 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4526 Opcode == ISD::ATOMIC_SWAP ||
4527 Opcode == ISD::ATOMIC_STORE) &&
4528 "Invalid Atomic Op");
4530 EVT VT = Val.getValueType();
4532 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4533 getVTList(VT, MVT::Other);
4534 SDValue Ops[] = {Chain, Ptr, Val};
4535 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4538 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4539 EVT VT, SDValue Chain,
4541 MachineMemOperand *MMO,
4542 AtomicOrdering Ordering,
4543 SynchronizationScope SynchScope) {
4544 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4546 SDVTList VTs = getVTList(VT, MVT::Other);
4547 SDValue Ops[] = {Chain, Ptr};
4548 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4551 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4552 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4553 if (Ops.size() == 1)
4556 SmallVector<EVT, 4> VTs;
4557 VTs.reserve(Ops.size());
4558 for (unsigned i = 0; i < Ops.size(); ++i)
4559 VTs.push_back(Ops[i].getValueType());
4560 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4564 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4565 ArrayRef<SDValue> Ops,
4566 EVT MemVT, MachinePointerInfo PtrInfo,
4567 unsigned Align, bool Vol,
4568 bool ReadMem, bool WriteMem, unsigned Size) {
4569 if (Align == 0) // Ensure that codegen never sees alignment 0
4570 Align = getEVTAlignment(MemVT);
4572 MachineFunction &MF = getMachineFunction();
4575 Flags |= MachineMemOperand::MOStore;
4577 Flags |= MachineMemOperand::MOLoad;
4579 Flags |= MachineMemOperand::MOVolatile;
4581 Size = MemVT.getStoreSize();
4582 MachineMemOperand *MMO =
4583 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4585 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4589 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4590 ArrayRef<SDValue> Ops, EVT MemVT,
4591 MachineMemOperand *MMO) {
4592 assert((Opcode == ISD::INTRINSIC_VOID ||
4593 Opcode == ISD::INTRINSIC_W_CHAIN ||
4594 Opcode == ISD::PREFETCH ||
4595 Opcode == ISD::LIFETIME_START ||
4596 Opcode == ISD::LIFETIME_END ||
4597 (Opcode <= INT_MAX &&
4598 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4599 "Opcode is not a memory-accessing opcode!");
4601 // Memoize the node unless it returns a flag.
4602 MemIntrinsicSDNode *N;
4603 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4604 FoldingSetNodeID ID;
4605 AddNodeIDNode(ID, Opcode, VTList, Ops);
4606 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4608 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4609 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4610 return SDValue(E, 0);
4613 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4614 dl.getDebugLoc(), VTList, Ops,
4616 CSEMap.InsertNode(N, IP);
4618 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4619 dl.getDebugLoc(), VTList, Ops,
4623 return SDValue(N, 0);
4626 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4627 /// MachinePointerInfo record from it. This is particularly useful because the
4628 /// code generator has many cases where it doesn't bother passing in a
4629 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4630 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4631 // If this is FI+Offset, we can model it.
4632 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4633 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4635 // If this is (FI+Offset1)+Offset2, we can model it.
4636 if (Ptr.getOpcode() != ISD::ADD ||
4637 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4638 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4639 return MachinePointerInfo();
4641 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4642 return MachinePointerInfo::getFixedStack(FI, Offset+
4643 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4646 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4647 /// MachinePointerInfo record from it. This is particularly useful because the
4648 /// code generator has many cases where it doesn't bother passing in a
4649 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4650 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4651 // If the 'Offset' value isn't a constant, we can't handle this.
4652 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4653 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4654 if (OffsetOp.getOpcode() == ISD::UNDEF)
4655 return InferPointerInfo(Ptr);
4656 return MachinePointerInfo();
4661 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4662 EVT VT, SDLoc dl, SDValue Chain,
4663 SDValue Ptr, SDValue Offset,
4664 MachinePointerInfo PtrInfo, EVT MemVT,
4665 bool isVolatile, bool isNonTemporal, bool isInvariant,
4666 unsigned Alignment, const AAMDNodes &AAInfo,
4667 const MDNode *Ranges) {
4668 assert(Chain.getValueType() == MVT::Other &&
4669 "Invalid chain type");
4670 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4671 Alignment = getEVTAlignment(VT);
4673 unsigned Flags = MachineMemOperand::MOLoad;
4675 Flags |= MachineMemOperand::MOVolatile;
4677 Flags |= MachineMemOperand::MONonTemporal;
4679 Flags |= MachineMemOperand::MOInvariant;
4681 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4683 if (PtrInfo.V.isNull())
4684 PtrInfo = InferPointerInfo(Ptr, Offset);
4686 MachineFunction &MF = getMachineFunction();
4687 MachineMemOperand *MMO =
4688 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4690 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4694 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4695 EVT VT, SDLoc dl, SDValue Chain,
4696 SDValue Ptr, SDValue Offset, EVT MemVT,
4697 MachineMemOperand *MMO) {
4699 ExtType = ISD::NON_EXTLOAD;
4700 } else if (ExtType == ISD::NON_EXTLOAD) {
4701 assert(VT == MemVT && "Non-extending load from different memory type!");
4704 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4705 "Should only be an extending load, not truncating!");
4706 assert(VT.isInteger() == MemVT.isInteger() &&
4707 "Cannot convert from FP to Int or Int -> FP!");
4708 assert(VT.isVector() == MemVT.isVector() &&
4709 "Cannot use trunc store to convert to or from a vector!");
4710 assert((!VT.isVector() ||
4711 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4712 "Cannot use trunc store to change the number of vector elements!");
4715 bool Indexed = AM != ISD::UNINDEXED;
4716 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4717 "Unindexed load with an offset!");
4719 SDVTList VTs = Indexed ?
4720 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4721 SDValue Ops[] = { Chain, Ptr, Offset };
4722 FoldingSetNodeID ID;
4723 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4724 ID.AddInteger(MemVT.getRawBits());
4725 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4726 MMO->isNonTemporal(),
4727 MMO->isInvariant()));
4728 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4730 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4731 cast<LoadSDNode>(E)->refineAlignment(MMO);
4732 return SDValue(E, 0);
4734 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4735 dl.getDebugLoc(), VTs, AM, ExtType,
4737 CSEMap.InsertNode(N, IP);
4739 return SDValue(N, 0);
4742 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4743 SDValue Chain, SDValue Ptr,
4744 MachinePointerInfo PtrInfo,
4745 bool isVolatile, bool isNonTemporal,
4746 bool isInvariant, unsigned Alignment,
4747 const AAMDNodes &AAInfo,
4748 const MDNode *Ranges) {
4749 SDValue Undef = getUNDEF(Ptr.getValueType());
4750 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4751 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4755 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4756 SDValue Chain, SDValue Ptr,
4757 MachineMemOperand *MMO) {
4758 SDValue Undef = getUNDEF(Ptr.getValueType());
4759 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4763 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4764 SDValue Chain, SDValue Ptr,
4765 MachinePointerInfo PtrInfo, EVT MemVT,
4766 bool isVolatile, bool isNonTemporal,
4767 bool isInvariant, unsigned Alignment,
4768 const AAMDNodes &AAInfo) {
4769 SDValue Undef = getUNDEF(Ptr.getValueType());
4770 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4771 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4776 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4777 SDValue Chain, SDValue Ptr, EVT MemVT,
4778 MachineMemOperand *MMO) {
4779 SDValue Undef = getUNDEF(Ptr.getValueType());
4780 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4785 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4786 SDValue Offset, ISD::MemIndexedMode AM) {
4787 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4788 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4789 "Load is already a indexed load!");
4790 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4791 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4792 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4793 false, LD->getAlignment());
4796 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4797 SDValue Ptr, MachinePointerInfo PtrInfo,
4798 bool isVolatile, bool isNonTemporal,
4799 unsigned Alignment, const AAMDNodes &AAInfo) {
4800 assert(Chain.getValueType() == MVT::Other &&
4801 "Invalid chain type");
4802 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4803 Alignment = getEVTAlignment(Val.getValueType());
4805 unsigned Flags = MachineMemOperand::MOStore;
4807 Flags |= MachineMemOperand::MOVolatile;
4809 Flags |= MachineMemOperand::MONonTemporal;
4811 if (PtrInfo.V.isNull())
4812 PtrInfo = InferPointerInfo(Ptr);
4814 MachineFunction &MF = getMachineFunction();
4815 MachineMemOperand *MMO =
4816 MF.getMachineMemOperand(PtrInfo, Flags,
4817 Val.getValueType().getStoreSize(), Alignment,
4820 return getStore(Chain, dl, Val, Ptr, MMO);
4823 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4824 SDValue Ptr, MachineMemOperand *MMO) {
4825 assert(Chain.getValueType() == MVT::Other &&
4826 "Invalid chain type");
4827 EVT VT = Val.getValueType();
4828 SDVTList VTs = getVTList(MVT::Other);
4829 SDValue Undef = getUNDEF(Ptr.getValueType());
4830 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4831 FoldingSetNodeID ID;
4832 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4833 ID.AddInteger(VT.getRawBits());
4834 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4835 MMO->isNonTemporal(), MMO->isInvariant()));
4836 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4838 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4839 cast<StoreSDNode>(E)->refineAlignment(MMO);
4840 return SDValue(E, 0);
4842 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4843 dl.getDebugLoc(), VTs,
4844 ISD::UNINDEXED, false, VT, MMO);
4845 CSEMap.InsertNode(N, IP);
4847 return SDValue(N, 0);
4850 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4851 SDValue Ptr, MachinePointerInfo PtrInfo,
4852 EVT SVT,bool isVolatile, bool isNonTemporal,
4854 const AAMDNodes &AAInfo) {
4855 assert(Chain.getValueType() == MVT::Other &&
4856 "Invalid chain type");
4857 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4858 Alignment = getEVTAlignment(SVT);
4860 unsigned Flags = MachineMemOperand::MOStore;
4862 Flags |= MachineMemOperand::MOVolatile;
4864 Flags |= MachineMemOperand::MONonTemporal;
4866 if (PtrInfo.V.isNull())
4867 PtrInfo = InferPointerInfo(Ptr);
4869 MachineFunction &MF = getMachineFunction();
4870 MachineMemOperand *MMO =
4871 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4874 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4877 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4878 SDValue Ptr, EVT SVT,
4879 MachineMemOperand *MMO) {
4880 EVT VT = Val.getValueType();
4882 assert(Chain.getValueType() == MVT::Other &&
4883 "Invalid chain type");
4885 return getStore(Chain, dl, Val, Ptr, MMO);
4887 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4888 "Should only be a truncating store, not extending!");
4889 assert(VT.isInteger() == SVT.isInteger() &&
4890 "Can't do FP-INT conversion!");
4891 assert(VT.isVector() == SVT.isVector() &&
4892 "Cannot use trunc store to convert to or from a vector!");
4893 assert((!VT.isVector() ||
4894 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4895 "Cannot use trunc store to change the number of vector elements!");
4897 SDVTList VTs = getVTList(MVT::Other);
4898 SDValue Undef = getUNDEF(Ptr.getValueType());
4899 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4900 FoldingSetNodeID ID;
4901 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4902 ID.AddInteger(SVT.getRawBits());
4903 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4904 MMO->isNonTemporal(), MMO->isInvariant()));
4905 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4907 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4908 cast<StoreSDNode>(E)->refineAlignment(MMO);
4909 return SDValue(E, 0);
4911 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4912 dl.getDebugLoc(), VTs,
4913 ISD::UNINDEXED, true, SVT, MMO);
4914 CSEMap.InsertNode(N, IP);
4916 return SDValue(N, 0);
4920 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4921 SDValue Offset, ISD::MemIndexedMode AM) {
4922 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4923 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4924 "Store is already a indexed store!");
4925 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4926 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4927 FoldingSetNodeID ID;
4928 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4929 ID.AddInteger(ST->getMemoryVT().getRawBits());
4930 ID.AddInteger(ST->getRawSubclassData());
4931 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4933 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4934 return SDValue(E, 0);
4936 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4937 dl.getDebugLoc(), VTs, AM,
4938 ST->isTruncatingStore(),
4940 ST->getMemOperand());
4941 CSEMap.InsertNode(N, IP);
4943 return SDValue(N, 0);
4947 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
4948 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
4949 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
4951 SDVTList VTs = getVTList(VT, MVT::Other);
4952 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
4953 FoldingSetNodeID ID;
4954 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
4955 ID.AddInteger(VT.getRawBits());
4956 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
4958 MMO->isNonTemporal(),
4959 MMO->isInvariant()));
4960 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4962 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4963 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
4964 return SDValue(E, 0);
4966 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
4967 dl.getDebugLoc(), Ops, 4, VTs,
4969 CSEMap.InsertNode(N, IP);
4971 return SDValue(N, 0);
4974 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
4975 SDValue Ptr, SDValue Mask, EVT MemVT,
4976 MachineMemOperand *MMO, bool isTrunc) {
4977 assert(Chain.getValueType() == MVT::Other &&
4978 "Invalid chain type");
4979 EVT VT = Val.getValueType();
4980 SDVTList VTs = getVTList(MVT::Other);
4981 SDValue Ops[] = { Chain, Ptr, Mask, Val };
4982 FoldingSetNodeID ID;
4983 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
4984 ID.AddInteger(VT.getRawBits());
4985 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4986 MMO->isNonTemporal(), MMO->isInvariant()));
4987 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4989 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4990 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
4991 return SDValue(E, 0);
4993 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
4994 dl.getDebugLoc(), Ops, 4,
4995 VTs, isTrunc, MemVT, MMO);
4996 CSEMap.InsertNode(N, IP);
4998 return SDValue(N, 0);
5001 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5002 SDValue Chain, SDValue Ptr,
5005 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5006 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5009 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5010 ArrayRef<SDUse> Ops) {
5011 switch (Ops.size()) {
5012 case 0: return getNode(Opcode, DL, VT);
5013 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5014 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5015 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5019 // Copy from an SDUse array into an SDValue array for use with
5020 // the regular getNode logic.
5021 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5022 return getNode(Opcode, DL, VT, NewOps);
5025 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5026 ArrayRef<SDValue> Ops) {
5027 unsigned NumOps = Ops.size();
5029 case 0: return getNode(Opcode, DL, VT);
5030 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5031 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5032 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5038 case ISD::SELECT_CC: {
5039 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5040 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5041 "LHS and RHS of condition must have same type!");
5042 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5043 "True and False arms of SelectCC must have same type!");
5044 assert(Ops[2].getValueType() == VT &&
5045 "select_cc node must be of same type as true and false value!");
5049 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5050 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5051 "LHS/RHS of comparison should match types!");
5058 SDVTList VTs = getVTList(VT);
5060 if (VT != MVT::Glue) {
5061 FoldingSetNodeID ID;
5062 AddNodeIDNode(ID, Opcode, VTs, Ops);
5065 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5066 return SDValue(E, 0);
5068 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5070 CSEMap.InsertNode(N, IP);
5072 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5077 return SDValue(N, 0);
5080 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5081 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5082 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5085 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5086 ArrayRef<SDValue> Ops) {
5087 if (VTList.NumVTs == 1)
5088 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5092 // FIXME: figure out how to safely handle things like
5093 // int foo(int x) { return 1 << (x & 255); }
5094 // int bar() { return foo(256); }
5095 case ISD::SRA_PARTS:
5096 case ISD::SRL_PARTS:
5097 case ISD::SHL_PARTS:
5098 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5099 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5100 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5101 else if (N3.getOpcode() == ISD::AND)
5102 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5103 // If the and is only masking out bits that cannot effect the shift,
5104 // eliminate the and.
5105 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5106 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5107 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5113 // Memoize the node unless it returns a flag.
5115 unsigned NumOps = Ops.size();
5116 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5117 FoldingSetNodeID ID;
5118 AddNodeIDNode(ID, Opcode, VTList, Ops);
5120 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5121 return SDValue(E, 0);
5124 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5125 DL.getDebugLoc(), VTList, Ops[0]);
5126 } else if (NumOps == 2) {
5127 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5128 DL.getDebugLoc(), VTList, Ops[0],
5130 } else if (NumOps == 3) {
5131 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5132 DL.getDebugLoc(), VTList, Ops[0],
5135 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5138 CSEMap.InsertNode(N, IP);
5141 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5142 DL.getDebugLoc(), VTList, Ops[0]);
5143 } else if (NumOps == 2) {
5144 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5145 DL.getDebugLoc(), VTList, Ops[0],
5147 } else if (NumOps == 3) {
5148 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5149 DL.getDebugLoc(), VTList, Ops[0],
5152 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5157 return SDValue(N, 0);
5160 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5161 return getNode(Opcode, DL, VTList, None);
5164 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5166 SDValue Ops[] = { N1 };
5167 return getNode(Opcode, DL, VTList, Ops);
5170 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5171 SDValue N1, SDValue N2) {
5172 SDValue Ops[] = { N1, N2 };
5173 return getNode(Opcode, DL, VTList, Ops);
5176 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5177 SDValue N1, SDValue N2, SDValue N3) {
5178 SDValue Ops[] = { N1, N2, N3 };
5179 return getNode(Opcode, DL, VTList, Ops);
5182 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5183 SDValue N1, SDValue N2, SDValue N3,
5185 SDValue Ops[] = { N1, N2, N3, N4 };
5186 return getNode(Opcode, DL, VTList, Ops);
5189 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5190 SDValue N1, SDValue N2, SDValue N3,
5191 SDValue N4, SDValue N5) {
5192 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5193 return getNode(Opcode, DL, VTList, Ops);
5196 SDVTList SelectionDAG::getVTList(EVT VT) {
5197 return makeVTList(SDNode::getValueTypeList(VT), 1);
5200 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5201 FoldingSetNodeID ID;
5203 ID.AddInteger(VT1.getRawBits());
5204 ID.AddInteger(VT2.getRawBits());
5207 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5209 EVT *Array = Allocator.Allocate<EVT>(2);
5212 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5213 VTListMap.InsertNode(Result, IP);
5215 return Result->getSDVTList();
5218 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5219 FoldingSetNodeID ID;
5221 ID.AddInteger(VT1.getRawBits());
5222 ID.AddInteger(VT2.getRawBits());
5223 ID.AddInteger(VT3.getRawBits());
5226 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5228 EVT *Array = Allocator.Allocate<EVT>(3);
5232 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5233 VTListMap.InsertNode(Result, IP);
5235 return Result->getSDVTList();
5238 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5239 FoldingSetNodeID ID;
5241 ID.AddInteger(VT1.getRawBits());
5242 ID.AddInteger(VT2.getRawBits());
5243 ID.AddInteger(VT3.getRawBits());
5244 ID.AddInteger(VT4.getRawBits());
5247 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5249 EVT *Array = Allocator.Allocate<EVT>(4);
5254 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5255 VTListMap.InsertNode(Result, IP);
5257 return Result->getSDVTList();
5260 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5261 unsigned NumVTs = VTs.size();
5262 FoldingSetNodeID ID;
5263 ID.AddInteger(NumVTs);
5264 for (unsigned index = 0; index < NumVTs; index++) {
5265 ID.AddInteger(VTs[index].getRawBits());
5269 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5271 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5272 std::copy(VTs.begin(), VTs.end(), Array);
5273 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5274 VTListMap.InsertNode(Result, IP);
5276 return Result->getSDVTList();
5280 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5281 /// specified operands. If the resultant node already exists in the DAG,
5282 /// this does not modify the specified node, instead it returns the node that
5283 /// already exists. If the resultant node does not exist in the DAG, the
5284 /// input node is returned. As a degenerate case, if you specify the same
5285 /// input operands as the node already has, the input node is returned.
5286 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5287 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5289 // Check to see if there is no change.
5290 if (Op == N->getOperand(0)) return N;
5292 // See if the modified node already exists.
5293 void *InsertPos = nullptr;
5294 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5297 // Nope it doesn't. Remove the node from its current place in the maps.
5299 if (!RemoveNodeFromCSEMaps(N))
5300 InsertPos = nullptr;
5302 // Now we update the operands.
5303 N->OperandList[0].set(Op);
5305 // If this gets put into a CSE map, add it.
5306 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5310 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5311 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5313 // Check to see if there is no change.
5314 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5315 return N; // No operands changed, just return the input node.
5317 // See if the modified node already exists.
5318 void *InsertPos = nullptr;
5319 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5322 // Nope it doesn't. Remove the node from its current place in the maps.
5324 if (!RemoveNodeFromCSEMaps(N))
5325 InsertPos = nullptr;
5327 // Now we update the operands.
5328 if (N->OperandList[0] != Op1)
5329 N->OperandList[0].set(Op1);
5330 if (N->OperandList[1] != Op2)
5331 N->OperandList[1].set(Op2);
5333 // If this gets put into a CSE map, add it.
5334 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5338 SDNode *SelectionDAG::
5339 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5340 SDValue Ops[] = { Op1, Op2, Op3 };
5341 return UpdateNodeOperands(N, Ops);
5344 SDNode *SelectionDAG::
5345 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5346 SDValue Op3, SDValue Op4) {
5347 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5348 return UpdateNodeOperands(N, Ops);
5351 SDNode *SelectionDAG::
5352 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5353 SDValue Op3, SDValue Op4, SDValue Op5) {
5354 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5355 return UpdateNodeOperands(N, Ops);
5358 SDNode *SelectionDAG::
5359 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5360 unsigned NumOps = Ops.size();
5361 assert(N->getNumOperands() == NumOps &&
5362 "Update with wrong number of operands");
5364 // Check to see if there is no change.
5365 bool AnyChange = false;
5366 for (unsigned i = 0; i != NumOps; ++i) {
5367 if (Ops[i] != N->getOperand(i)) {
5373 // No operands changed, just return the input node.
5374 if (!AnyChange) return N;
5376 // See if the modified node already exists.
5377 void *InsertPos = nullptr;
5378 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5381 // Nope it doesn't. Remove the node from its current place in the maps.
5383 if (!RemoveNodeFromCSEMaps(N))
5384 InsertPos = nullptr;
5386 // Now we update the operands.
5387 for (unsigned i = 0; i != NumOps; ++i)
5388 if (N->OperandList[i] != Ops[i])
5389 N->OperandList[i].set(Ops[i]);
5391 // If this gets put into a CSE map, add it.
5392 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5396 /// DropOperands - Release the operands and set this node to have
5398 void SDNode::DropOperands() {
5399 // Unlike the code in MorphNodeTo that does this, we don't need to
5400 // watch for dead nodes here.
5401 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5407 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5410 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5412 SDVTList VTs = getVTList(VT);
5413 return SelectNodeTo(N, MachineOpc, VTs, None);
5416 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5417 EVT VT, SDValue Op1) {
5418 SDVTList VTs = getVTList(VT);
5419 SDValue Ops[] = { Op1 };
5420 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5423 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5424 EVT VT, SDValue Op1,
5426 SDVTList VTs = getVTList(VT);
5427 SDValue Ops[] = { Op1, Op2 };
5428 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5431 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5432 EVT VT, SDValue Op1,
5433 SDValue Op2, SDValue Op3) {
5434 SDVTList VTs = getVTList(VT);
5435 SDValue Ops[] = { Op1, Op2, Op3 };
5436 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5439 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5440 EVT VT, ArrayRef<SDValue> Ops) {
5441 SDVTList VTs = getVTList(VT);
5442 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5445 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5446 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5447 SDVTList VTs = getVTList(VT1, VT2);
5448 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5451 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5453 SDVTList VTs = getVTList(VT1, VT2);
5454 return SelectNodeTo(N, MachineOpc, VTs, None);
5457 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5458 EVT VT1, EVT VT2, EVT VT3,
5459 ArrayRef<SDValue> Ops) {
5460 SDVTList VTs = getVTList(VT1, VT2, VT3);
5461 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5464 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5465 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5466 ArrayRef<SDValue> Ops) {
5467 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5468 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5471 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5474 SDVTList VTs = getVTList(VT1, VT2);
5475 SDValue Ops[] = { Op1 };
5476 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5479 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5481 SDValue Op1, SDValue Op2) {
5482 SDVTList VTs = getVTList(VT1, VT2);
5483 SDValue Ops[] = { Op1, Op2 };
5484 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5487 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5489 SDValue Op1, SDValue Op2,
5491 SDVTList VTs = getVTList(VT1, VT2);
5492 SDValue Ops[] = { Op1, Op2, Op3 };
5493 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5496 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5497 EVT VT1, EVT VT2, EVT VT3,
5498 SDValue Op1, SDValue Op2,
5500 SDVTList VTs = getVTList(VT1, VT2, VT3);
5501 SDValue Ops[] = { Op1, Op2, Op3 };
5502 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5505 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5506 SDVTList VTs,ArrayRef<SDValue> Ops) {
5507 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5508 // Reset the NodeID to -1.
5513 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5514 /// the line number information on the merged node since it is not possible to
5515 /// preserve the information that operation is associated with multiple lines.
5516 /// This will make the debugger working better at -O0, were there is a higher
5517 /// probability having other instructions associated with that line.
5519 /// For IROrder, we keep the smaller of the two
5520 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5521 DebugLoc NLoc = N->getDebugLoc();
5522 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5523 (OLoc.getDebugLoc() != NLoc)) {
5524 N->setDebugLoc(DebugLoc());
5526 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5527 N->setIROrder(Order);
5531 /// MorphNodeTo - This *mutates* the specified node to have the specified
5532 /// return type, opcode, and operands.
5534 /// Note that MorphNodeTo returns the resultant node. If there is already a
5535 /// node of the specified opcode and operands, it returns that node instead of
5536 /// the current one. Note that the SDLoc need not be the same.
5538 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5539 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5540 /// node, and because it doesn't require CSE recalculation for any of
5541 /// the node's users.
5543 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5544 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5545 /// the legalizer which maintain worklists that would need to be updated when
5546 /// deleting things.
5547 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5548 SDVTList VTs, ArrayRef<SDValue> Ops) {
5549 unsigned NumOps = Ops.size();
5550 // If an identical node already exists, use it.
5552 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5553 FoldingSetNodeID ID;
5554 AddNodeIDNode(ID, Opc, VTs, Ops);
5555 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5556 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5559 if (!RemoveNodeFromCSEMaps(N))
5562 // Start the morphing.
5564 N->ValueList = VTs.VTs;
5565 N->NumValues = VTs.NumVTs;
5567 // Clear the operands list, updating used nodes to remove this from their
5568 // use list. Keep track of any operands that become dead as a result.
5569 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5570 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5572 SDNode *Used = Use.getNode();
5574 if (Used->use_empty())
5575 DeadNodeSet.insert(Used);
5578 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5579 // Initialize the memory references information.
5580 MN->setMemRefs(nullptr, nullptr);
5581 // If NumOps is larger than the # of operands we can have in a
5582 // MachineSDNode, reallocate the operand list.
5583 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5584 if (MN->OperandsNeedDelete)
5585 delete[] MN->OperandList;
5586 if (NumOps > array_lengthof(MN->LocalOperands))
5587 // We're creating a final node that will live unmorphed for the
5588 // remainder of the current SelectionDAG iteration, so we can allocate
5589 // the operands directly out of a pool with no recycling metadata.
5590 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5591 Ops.data(), NumOps);
5593 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5594 MN->OperandsNeedDelete = false;
5596 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5598 // If NumOps is larger than the # of operands we currently have, reallocate
5599 // the operand list.
5600 if (NumOps > N->NumOperands) {
5601 if (N->OperandsNeedDelete)
5602 delete[] N->OperandList;
5603 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5604 N->OperandsNeedDelete = true;
5606 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5609 // Delete any nodes that are still dead after adding the uses for the
5611 if (!DeadNodeSet.empty()) {
5612 SmallVector<SDNode *, 16> DeadNodes;
5613 for (SDNode *N : DeadNodeSet)
5615 DeadNodes.push_back(N);
5616 RemoveDeadNodes(DeadNodes);
5620 CSEMap.InsertNode(N, IP); // Memoize the new node.
5625 /// getMachineNode - These are used for target selectors to create a new node
5626 /// with specified return type(s), MachineInstr opcode, and operands.
5628 /// Note that getMachineNode returns the resultant node. If there is already a
5629 /// node of the specified opcode and operands, it returns that node instead of
5630 /// the current one.
5632 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5633 SDVTList VTs = getVTList(VT);
5634 return getMachineNode(Opcode, dl, VTs, None);
5638 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5639 SDVTList VTs = getVTList(VT);
5640 SDValue Ops[] = { Op1 };
5641 return getMachineNode(Opcode, dl, VTs, Ops);
5645 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5646 SDValue Op1, SDValue Op2) {
5647 SDVTList VTs = getVTList(VT);
5648 SDValue Ops[] = { Op1, Op2 };
5649 return getMachineNode(Opcode, dl, VTs, Ops);
5653 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5654 SDValue Op1, SDValue Op2, SDValue Op3) {
5655 SDVTList VTs = getVTList(VT);
5656 SDValue Ops[] = { Op1, Op2, Op3 };
5657 return getMachineNode(Opcode, dl, VTs, Ops);
5661 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5662 ArrayRef<SDValue> Ops) {
5663 SDVTList VTs = getVTList(VT);
5664 return getMachineNode(Opcode, dl, VTs, Ops);
5668 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5669 SDVTList VTs = getVTList(VT1, VT2);
5670 return getMachineNode(Opcode, dl, VTs, None);
5674 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5675 EVT VT1, EVT VT2, SDValue Op1) {
5676 SDVTList VTs = getVTList(VT1, VT2);
5677 SDValue Ops[] = { Op1 };
5678 return getMachineNode(Opcode, dl, VTs, Ops);
5682 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5683 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5684 SDVTList VTs = getVTList(VT1, VT2);
5685 SDValue Ops[] = { Op1, Op2 };
5686 return getMachineNode(Opcode, dl, VTs, Ops);
5690 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5691 EVT VT1, EVT VT2, SDValue Op1,
5692 SDValue Op2, SDValue Op3) {
5693 SDVTList VTs = getVTList(VT1, VT2);
5694 SDValue Ops[] = { Op1, Op2, Op3 };
5695 return getMachineNode(Opcode, dl, VTs, Ops);
5699 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5701 ArrayRef<SDValue> Ops) {
5702 SDVTList VTs = getVTList(VT1, VT2);
5703 return getMachineNode(Opcode, dl, VTs, Ops);
5707 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5708 EVT VT1, EVT VT2, EVT VT3,
5709 SDValue Op1, SDValue Op2) {
5710 SDVTList VTs = getVTList(VT1, VT2, VT3);
5711 SDValue Ops[] = { Op1, Op2 };
5712 return getMachineNode(Opcode, dl, VTs, Ops);
5716 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5717 EVT VT1, EVT VT2, EVT VT3,
5718 SDValue Op1, SDValue Op2, SDValue Op3) {
5719 SDVTList VTs = getVTList(VT1, VT2, VT3);
5720 SDValue Ops[] = { Op1, Op2, Op3 };
5721 return getMachineNode(Opcode, dl, VTs, Ops);
5725 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5726 EVT VT1, EVT VT2, EVT VT3,
5727 ArrayRef<SDValue> Ops) {
5728 SDVTList VTs = getVTList(VT1, VT2, VT3);
5729 return getMachineNode(Opcode, dl, VTs, Ops);
5733 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5734 EVT VT2, EVT VT3, EVT VT4,
5735 ArrayRef<SDValue> Ops) {
5736 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5737 return getMachineNode(Opcode, dl, VTs, Ops);
5741 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5742 ArrayRef<EVT> ResultTys,
5743 ArrayRef<SDValue> Ops) {
5744 SDVTList VTs = getVTList(ResultTys);
5745 return getMachineNode(Opcode, dl, VTs, Ops);
5749 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5750 ArrayRef<SDValue> OpsArray) {
5751 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5754 const SDValue *Ops = OpsArray.data();
5755 unsigned NumOps = OpsArray.size();
5758 FoldingSetNodeID ID;
5759 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5761 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5762 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5766 // Allocate a new MachineSDNode.
5767 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5768 DL.getDebugLoc(), VTs);
5770 // Initialize the operands list.
5771 if (NumOps > array_lengthof(N->LocalOperands))
5772 // We're creating a final node that will live unmorphed for the
5773 // remainder of the current SelectionDAG iteration, so we can allocate
5774 // the operands directly out of a pool with no recycling metadata.
5775 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5778 N->InitOperands(N->LocalOperands, Ops, NumOps);
5779 N->OperandsNeedDelete = false;
5782 CSEMap.InsertNode(N, IP);
5788 /// getTargetExtractSubreg - A convenience function for creating
5789 /// TargetOpcode::EXTRACT_SUBREG nodes.
5791 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5793 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5794 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5795 VT, Operand, SRIdxVal);
5796 return SDValue(Subreg, 0);
5799 /// getTargetInsertSubreg - A convenience function for creating
5800 /// TargetOpcode::INSERT_SUBREG nodes.
5802 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5803 SDValue Operand, SDValue Subreg) {
5804 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5805 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5806 VT, Operand, Subreg, SRIdxVal);
5807 return SDValue(Result, 0);
5810 /// getNodeIfExists - Get the specified node if it's already available, or
5811 /// else return NULL.
5812 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5813 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5815 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5816 FoldingSetNodeID ID;
5817 AddNodeIDNode(ID, Opcode, VTList, Ops);
5818 if (isBinOpWithFlags(Opcode))
5819 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5821 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5827 /// getDbgValue - Creates a SDDbgValue node.
5830 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5831 unsigned R, bool IsIndirect, uint64_t Off,
5832 DebugLoc DL, unsigned O) {
5833 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5837 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5838 const Value *C, uint64_t Off,
5839 DebugLoc DL, unsigned O) {
5840 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5844 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5845 unsigned FI, uint64_t Off,
5846 DebugLoc DL, unsigned O) {
5847 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5852 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5853 /// pointed to by a use iterator is deleted, increment the use iterator
5854 /// so that it doesn't dangle.
5856 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5857 SDNode::use_iterator &UI;
5858 SDNode::use_iterator &UE;
5860 void NodeDeleted(SDNode *N, SDNode *E) override {
5861 // Increment the iterator as needed.
5862 while (UI != UE && N == *UI)
5867 RAUWUpdateListener(SelectionDAG &d,
5868 SDNode::use_iterator &ui,
5869 SDNode::use_iterator &ue)
5870 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5875 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5876 /// This can cause recursive merging of nodes in the DAG.
5878 /// This version assumes From has a single result value.
5880 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5881 SDNode *From = FromN.getNode();
5882 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5883 "Cannot replace with this method!");
5884 assert(From != To.getNode() && "Cannot replace uses of with self");
5886 // Iterate over all the existing uses of From. New uses will be added
5887 // to the beginning of the use list, which we avoid visiting.
5888 // This specifically avoids visiting uses of From that arise while the
5889 // replacement is happening, because any such uses would be the result
5890 // of CSE: If an existing node looks like From after one of its operands
5891 // is replaced by To, we don't want to replace of all its users with To
5892 // too. See PR3018 for more info.
5893 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5894 RAUWUpdateListener Listener(*this, UI, UE);
5898 // This node is about to morph, remove its old self from the CSE maps.
5899 RemoveNodeFromCSEMaps(User);
5901 // A user can appear in a use list multiple times, and when this
5902 // happens the uses are usually next to each other in the list.
5903 // To help reduce the number of CSE recomputations, process all
5904 // the uses of this user that we can find this way.
5906 SDUse &Use = UI.getUse();
5909 } while (UI != UE && *UI == User);
5911 // Now that we have modified User, add it back to the CSE maps. If it
5912 // already exists there, recursively merge the results together.
5913 AddModifiedNodeToCSEMaps(User);
5916 // If we just RAUW'd the root, take note.
5917 if (FromN == getRoot())
5921 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5922 /// This can cause recursive merging of nodes in the DAG.
5924 /// This version assumes that for each value of From, there is a
5925 /// corresponding value in To in the same position with the same type.
5927 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5929 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5930 assert((!From->hasAnyUseOfValue(i) ||
5931 From->getValueType(i) == To->getValueType(i)) &&
5932 "Cannot use this version of ReplaceAllUsesWith!");
5935 // Handle the trivial case.
5939 // Iterate over just the existing users of From. See the comments in
5940 // the ReplaceAllUsesWith above.
5941 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5942 RAUWUpdateListener Listener(*this, UI, UE);
5946 // This node is about to morph, remove its old self from the CSE maps.
5947 RemoveNodeFromCSEMaps(User);
5949 // A user can appear in a use list multiple times, and when this
5950 // happens the uses are usually next to each other in the list.
5951 // To help reduce the number of CSE recomputations, process all
5952 // the uses of this user that we can find this way.
5954 SDUse &Use = UI.getUse();
5957 } while (UI != UE && *UI == User);
5959 // Now that we have modified User, add it back to the CSE maps. If it
5960 // already exists there, recursively merge the results together.
5961 AddModifiedNodeToCSEMaps(User);
5964 // If we just RAUW'd the root, take note.
5965 if (From == getRoot().getNode())
5966 setRoot(SDValue(To, getRoot().getResNo()));
5969 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5970 /// This can cause recursive merging of nodes in the DAG.
5972 /// This version can replace From with any result values. To must match the
5973 /// number and types of values returned by From.
5974 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5975 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5976 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5978 // Iterate over just the existing users of From. See the comments in
5979 // the ReplaceAllUsesWith above.
5980 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5981 RAUWUpdateListener Listener(*this, UI, UE);
5985 // This node is about to morph, remove its old self from the CSE maps.
5986 RemoveNodeFromCSEMaps(User);
5988 // A user can appear in a use list multiple times, and when this
5989 // happens the uses are usually next to each other in the list.
5990 // To help reduce the number of CSE recomputations, process all
5991 // the uses of this user that we can find this way.
5993 SDUse &Use = UI.getUse();
5994 const SDValue &ToOp = To[Use.getResNo()];
5997 } while (UI != UE && *UI == User);
5999 // Now that we have modified User, add it back to the CSE maps. If it
6000 // already exists there, recursively merge the results together.
6001 AddModifiedNodeToCSEMaps(User);
6004 // If we just RAUW'd the root, take note.
6005 if (From == getRoot().getNode())
6006 setRoot(SDValue(To[getRoot().getResNo()]));
6009 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6010 /// uses of other values produced by From.getNode() alone. The Deleted
6011 /// vector is handled the same way as for ReplaceAllUsesWith.
6012 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6013 // Handle the really simple, really trivial case efficiently.
6014 if (From == To) return;
6016 // Handle the simple, trivial, case efficiently.
6017 if (From.getNode()->getNumValues() == 1) {
6018 ReplaceAllUsesWith(From, To);
6022 // Iterate over just the existing users of From. See the comments in
6023 // the ReplaceAllUsesWith above.
6024 SDNode::use_iterator UI = From.getNode()->use_begin(),
6025 UE = From.getNode()->use_end();
6026 RAUWUpdateListener Listener(*this, UI, UE);
6029 bool UserRemovedFromCSEMaps = false;
6031 // A user can appear in a use list multiple times, and when this
6032 // happens the uses are usually next to each other in the list.
6033 // To help reduce the number of CSE recomputations, process all
6034 // the uses of this user that we can find this way.
6036 SDUse &Use = UI.getUse();
6038 // Skip uses of different values from the same node.
6039 if (Use.getResNo() != From.getResNo()) {
6044 // If this node hasn't been modified yet, it's still in the CSE maps,
6045 // so remove its old self from the CSE maps.
6046 if (!UserRemovedFromCSEMaps) {
6047 RemoveNodeFromCSEMaps(User);
6048 UserRemovedFromCSEMaps = true;
6053 } while (UI != UE && *UI == User);
6055 // We are iterating over all uses of the From node, so if a use
6056 // doesn't use the specific value, no changes are made.
6057 if (!UserRemovedFromCSEMaps)
6060 // Now that we have modified User, add it back to the CSE maps. If it
6061 // already exists there, recursively merge the results together.
6062 AddModifiedNodeToCSEMaps(User);
6065 // If we just RAUW'd the root, take note.
6066 if (From == getRoot())
6071 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6072 /// to record information about a use.
6079 /// operator< - Sort Memos by User.
6080 bool operator<(const UseMemo &L, const UseMemo &R) {
6081 return (intptr_t)L.User < (intptr_t)R.User;
6085 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6086 /// uses of other values produced by From.getNode() alone. The same value
6087 /// may appear in both the From and To list. The Deleted vector is
6088 /// handled the same way as for ReplaceAllUsesWith.
6089 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6092 // Handle the simple, trivial case efficiently.
6094 return ReplaceAllUsesOfValueWith(*From, *To);
6096 // Read up all the uses and make records of them. This helps
6097 // processing new uses that are introduced during the
6098 // replacement process.
6099 SmallVector<UseMemo, 4> Uses;
6100 for (unsigned i = 0; i != Num; ++i) {
6101 unsigned FromResNo = From[i].getResNo();
6102 SDNode *FromNode = From[i].getNode();
6103 for (SDNode::use_iterator UI = FromNode->use_begin(),
6104 E = FromNode->use_end(); UI != E; ++UI) {
6105 SDUse &Use = UI.getUse();
6106 if (Use.getResNo() == FromResNo) {
6107 UseMemo Memo = { *UI, i, &Use };
6108 Uses.push_back(Memo);
6113 // Sort the uses, so that all the uses from a given User are together.
6114 std::sort(Uses.begin(), Uses.end());
6116 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6117 UseIndex != UseIndexEnd; ) {
6118 // We know that this user uses some value of From. If it is the right
6119 // value, update it.
6120 SDNode *User = Uses[UseIndex].User;
6122 // This node is about to morph, remove its old self from the CSE maps.
6123 RemoveNodeFromCSEMaps(User);
6125 // The Uses array is sorted, so all the uses for a given User
6126 // are next to each other in the list.
6127 // To help reduce the number of CSE recomputations, process all
6128 // the uses of this user that we can find this way.
6130 unsigned i = Uses[UseIndex].Index;
6131 SDUse &Use = *Uses[UseIndex].Use;
6135 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6137 // Now that we have modified User, add it back to the CSE maps. If it
6138 // already exists there, recursively merge the results together.
6139 AddModifiedNodeToCSEMaps(User);
6143 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6144 /// based on their topological order. It returns the maximum id and a vector
6145 /// of the SDNodes* in assigned order by reference.
6146 unsigned SelectionDAG::AssignTopologicalOrder() {
6148 unsigned DAGSize = 0;
6150 // SortedPos tracks the progress of the algorithm. Nodes before it are
6151 // sorted, nodes after it are unsorted. When the algorithm completes
6152 // it is at the end of the list.
6153 allnodes_iterator SortedPos = allnodes_begin();
6155 // Visit all the nodes. Move nodes with no operands to the front of
6156 // the list immediately. Annotate nodes that do have operands with their
6157 // operand count. Before we do this, the Node Id fields of the nodes
6158 // may contain arbitrary values. After, the Node Id fields for nodes
6159 // before SortedPos will contain the topological sort index, and the
6160 // Node Id fields for nodes At SortedPos and after will contain the
6161 // count of outstanding operands.
6162 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6164 checkForCycles(N, this);
6165 unsigned Degree = N->getNumOperands();
6167 // A node with no uses, add it to the result array immediately.
6168 N->setNodeId(DAGSize++);
6169 allnodes_iterator Q = N;
6171 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6172 assert(SortedPos != AllNodes.end() && "Overran node list");
6175 // Temporarily use the Node Id as scratch space for the degree count.
6176 N->setNodeId(Degree);
6180 // Visit all the nodes. As we iterate, move nodes into sorted order,
6181 // such that by the time the end is reached all nodes will be sorted.
6182 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6184 checkForCycles(N, this);
6185 // N is in sorted position, so all its uses have one less operand
6186 // that needs to be sorted.
6187 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6190 unsigned Degree = P->getNodeId();
6191 assert(Degree != 0 && "Invalid node degree");
6194 // All of P's operands are sorted, so P may sorted now.
6195 P->setNodeId(DAGSize++);
6197 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6198 assert(SortedPos != AllNodes.end() && "Overran node list");
6201 // Update P's outstanding operand count.
6202 P->setNodeId(Degree);
6205 if (I == SortedPos) {
6208 dbgs() << "Overran sorted position:\n";
6209 S->dumprFull(this); dbgs() << "\n";
6210 dbgs() << "Checking if this is due to cycles\n";
6211 checkForCycles(this, true);
6213 llvm_unreachable(nullptr);
6217 assert(SortedPos == AllNodes.end() &&
6218 "Topological sort incomplete!");
6219 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6220 "First node in topological sort is not the entry token!");
6221 assert(AllNodes.front().getNodeId() == 0 &&
6222 "First node in topological sort has non-zero id!");
6223 assert(AllNodes.front().getNumOperands() == 0 &&
6224 "First node in topological sort has operands!");
6225 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6226 "Last node in topologic sort has unexpected id!");
6227 assert(AllNodes.back().use_empty() &&
6228 "Last node in topologic sort has users!");
6229 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6233 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6234 /// value is produced by SD.
6235 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6237 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6238 SD->setHasDebugValue(true);
6240 DbgInfo->add(DB, SD, isParameter);
6243 /// TransferDbgValues - Transfer SDDbgValues.
6244 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6245 if (From == To || !From.getNode()->getHasDebugValue())
6247 SDNode *FromNode = From.getNode();
6248 SDNode *ToNode = To.getNode();
6249 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6250 SmallVector<SDDbgValue *, 2> ClonedDVs;
6251 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6253 SDDbgValue *Dbg = *I;
6254 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6256 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6257 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6258 Dbg->getDebugLoc(), Dbg->getOrder());
6259 ClonedDVs.push_back(Clone);
6262 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6263 E = ClonedDVs.end(); I != E; ++I)
6264 AddDbgValue(*I, ToNode, false);
6267 //===----------------------------------------------------------------------===//
6269 //===----------------------------------------------------------------------===//
6271 HandleSDNode::~HandleSDNode() {
6275 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6276 DebugLoc DL, const GlobalValue *GA,
6277 EVT VT, int64_t o, unsigned char TF)
6278 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6282 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6283 SDValue X, unsigned SrcAS,
6285 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6286 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6288 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6289 EVT memvt, MachineMemOperand *mmo)
6290 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6291 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6292 MMO->isNonTemporal(), MMO->isInvariant());
6293 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6294 assert(isNonTemporal() == MMO->isNonTemporal() &&
6295 "Non-temporal encoding error!");
6296 // We check here that the size of the memory operand fits within the size of
6297 // the MMO. This is because the MMO might indicate only a possible address
6298 // range instead of specifying the affected memory addresses precisely.
6299 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6302 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6303 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6304 : SDNode(Opc, Order, dl, VTs, Ops),
6305 MemoryVT(memvt), MMO(mmo) {
6306 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6307 MMO->isNonTemporal(), MMO->isInvariant());
6308 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6309 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6312 /// Profile - Gather unique data for the node.
6314 void SDNode::Profile(FoldingSetNodeID &ID) const {
6315 AddNodeIDNode(ID, this);
6320 std::vector<EVT> VTs;
6323 VTs.reserve(MVT::LAST_VALUETYPE);
6324 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6325 VTs.push_back(MVT((MVT::SimpleValueType)i));
6330 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6331 static ManagedStatic<EVTArray> SimpleVTArray;
6332 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6334 /// getValueTypeList - Return a pointer to the specified value type.
6336 const EVT *SDNode::getValueTypeList(EVT VT) {
6337 if (VT.isExtended()) {
6338 sys::SmartScopedLock<true> Lock(*VTMutex);
6339 return &(*EVTs->insert(VT).first);
6341 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6342 "Value type out of range!");
6343 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6347 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6348 /// indicated value. This method ignores uses of other values defined by this
6350 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6351 assert(Value < getNumValues() && "Bad value!");
6353 // TODO: Only iterate over uses of a given value of the node
6354 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6355 if (UI.getUse().getResNo() == Value) {
6362 // Found exactly the right number of uses?
6367 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6368 /// value. This method ignores uses of other values defined by this operation.
6369 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6370 assert(Value < getNumValues() && "Bad value!");
6372 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6373 if (UI.getUse().getResNo() == Value)
6380 /// isOnlyUserOf - Return true if this node is the only use of N.
6382 bool SDNode::isOnlyUserOf(SDNode *N) const {
6384 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6395 /// isOperand - Return true if this node is an operand of N.
6397 bool SDValue::isOperandOf(SDNode *N) const {
6398 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6399 if (*this == N->getOperand(i))
6404 bool SDNode::isOperandOf(SDNode *N) const {
6405 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6406 if (this == N->OperandList[i].getNode())
6411 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6412 /// be a chain) reaches the specified operand without crossing any
6413 /// side-effecting instructions on any chain path. In practice, this looks
6414 /// through token factors and non-volatile loads. In order to remain efficient,
6415 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6416 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6417 unsigned Depth) const {
6418 if (*this == Dest) return true;
6420 // Don't search too deeply, we just want to be able to see through
6421 // TokenFactor's etc.
6422 if (Depth == 0) return false;
6424 // If this is a token factor, all inputs to the TF happen in parallel. If any
6425 // of the operands of the TF does not reach dest, then we cannot do the xform.
6426 if (getOpcode() == ISD::TokenFactor) {
6427 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6428 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6433 // Loads don't have side effects, look through them.
6434 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6435 if (!Ld->isVolatile())
6436 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6441 /// hasPredecessor - Return true if N is a predecessor of this node.
6442 /// N is either an operand of this node, or can be reached by recursively
6443 /// traversing up the operands.
6444 /// NOTE: This is an expensive method. Use it carefully.
6445 bool SDNode::hasPredecessor(const SDNode *N) const {
6446 SmallPtrSet<const SDNode *, 32> Visited;
6447 SmallVector<const SDNode *, 16> Worklist;
6448 return hasPredecessorHelper(N, Visited, Worklist);
6452 SDNode::hasPredecessorHelper(const SDNode *N,
6453 SmallPtrSetImpl<const SDNode *> &Visited,
6454 SmallVectorImpl<const SDNode *> &Worklist) const {
6455 if (Visited.empty()) {
6456 Worklist.push_back(this);
6458 // Take a look in the visited set. If we've already encountered this node
6459 // we needn't search further.
6460 if (Visited.count(N))
6464 // Haven't visited N yet. Continue the search.
6465 while (!Worklist.empty()) {
6466 const SDNode *M = Worklist.pop_back_val();
6467 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6468 SDNode *Op = M->getOperand(i).getNode();
6469 if (Visited.insert(Op).second)
6470 Worklist.push_back(Op);
6479 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6480 assert(Num < NumOperands && "Invalid child # of SDNode!");
6481 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6484 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6485 assert(N->getNumValues() == 1 &&
6486 "Can't unroll a vector with multiple results!");
6488 EVT VT = N->getValueType(0);
6489 unsigned NE = VT.getVectorNumElements();
6490 EVT EltVT = VT.getVectorElementType();
6493 SmallVector<SDValue, 8> Scalars;
6494 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6496 // If ResNE is 0, fully unroll the vector op.
6499 else if (NE > ResNE)
6503 for (i= 0; i != NE; ++i) {
6504 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6505 SDValue Operand = N->getOperand(j);
6506 EVT OperandVT = Operand.getValueType();
6507 if (OperandVT.isVector()) {
6508 // A vector operand; extract a single element.
6509 EVT OperandEltVT = OperandVT.getVectorElementType();
6510 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6513 getConstant(i, TLI->getVectorIdxTy()));
6515 // A scalar operand; just use it as is.
6516 Operands[j] = Operand;
6520 switch (N->getOpcode()) {
6522 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6525 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6532 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6533 getShiftAmountOperand(Operands[0].getValueType(),
6536 case ISD::SIGN_EXTEND_INREG:
6537 case ISD::FP_ROUND_INREG: {
6538 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6539 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6541 getValueType(ExtVT)));
6546 for (; i < ResNE; ++i)
6547 Scalars.push_back(getUNDEF(EltVT));
6549 return getNode(ISD::BUILD_VECTOR, dl,
6550 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6554 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6555 /// location that is 'Dist' units away from the location that the 'Base' load
6556 /// is loading from.
6557 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6558 unsigned Bytes, int Dist) const {
6559 if (LD->getChain() != Base->getChain())
6561 EVT VT = LD->getValueType(0);
6562 if (VT.getSizeInBits() / 8 != Bytes)
6565 SDValue Loc = LD->getOperand(1);
6566 SDValue BaseLoc = Base->getOperand(1);
6567 if (Loc.getOpcode() == ISD::FrameIndex) {
6568 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6570 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6571 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6572 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6573 int FS = MFI->getObjectSize(FI);
6574 int BFS = MFI->getObjectSize(BFI);
6575 if (FS != BFS || FS != (int)Bytes) return false;
6576 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6580 if (isBaseWithConstantOffset(Loc)) {
6581 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6582 if (Loc.getOperand(0) == BaseLoc) {
6583 // If the base location is a simple address with no offset itself, then
6584 // the second load's first add operand should be the base address.
6585 if (LocOffset == Dist * (int)Bytes)
6587 } else if (isBaseWithConstantOffset(BaseLoc)) {
6588 // The base location itself has an offset, so subtract that value from the
6589 // second load's offset before comparing to distance * size.
6591 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6592 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6593 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6598 const GlobalValue *GV1 = nullptr;
6599 const GlobalValue *GV2 = nullptr;
6600 int64_t Offset1 = 0;
6601 int64_t Offset2 = 0;
6602 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6603 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6604 if (isGA1 && isGA2 && GV1 == GV2)
6605 return Offset1 == (Offset2 + Dist*Bytes);
6610 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6611 /// it cannot be inferred.
6612 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6613 // If this is a GlobalAddress + cst, return the alignment.
6614 const GlobalValue *GV;
6615 int64_t GVOffset = 0;
6616 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6617 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6618 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6619 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6620 TLI->getDataLayout());
6621 unsigned AlignBits = KnownZero.countTrailingOnes();
6622 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6624 return MinAlign(Align, GVOffset);
6627 // If this is a direct reference to a stack slot, use information about the
6628 // stack slot's alignment.
6629 int FrameIdx = 1 << 31;
6630 int64_t FrameOffset = 0;
6631 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6632 FrameIdx = FI->getIndex();
6633 } else if (isBaseWithConstantOffset(Ptr) &&
6634 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6636 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6637 FrameOffset = Ptr.getConstantOperandVal(1);
6640 if (FrameIdx != (1 << 31)) {
6641 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6642 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6650 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6651 /// which is split (or expanded) into two not necessarily identical pieces.
6652 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6653 // Currently all types are split in half.
6655 if (!VT.isVector()) {
6656 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6658 unsigned NumElements = VT.getVectorNumElements();
6659 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6660 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6663 return std::make_pair(LoVT, HiVT);
6666 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6668 std::pair<SDValue, SDValue>
6669 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6671 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6672 N.getValueType().getVectorNumElements() &&
6673 "More vector elements requested than available!");
6675 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6676 getConstant(0, TLI->getVectorIdxTy()));
6677 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6678 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6679 return std::make_pair(Lo, Hi);
6682 void SelectionDAG::ExtractVectorElements(SDValue Op,
6683 SmallVectorImpl<SDValue> &Args,
6684 unsigned Start, unsigned Count) {
6685 EVT VT = Op.getValueType();
6687 Count = VT.getVectorNumElements();
6689 EVT EltVT = VT.getVectorElementType();
6690 EVT IdxTy = TLI->getVectorIdxTy();
6692 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6693 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6694 Op, getConstant(i, IdxTy)));
6698 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6699 unsigned GlobalAddressSDNode::getAddressSpace() const {
6700 return getGlobal()->getType()->getAddressSpace();
6704 Type *ConstantPoolSDNode::getType() const {
6705 if (isMachineConstantPoolEntry())
6706 return Val.MachineCPVal->getType();
6707 return Val.ConstVal->getType();
6710 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6712 unsigned &SplatBitSize,
6714 unsigned MinSplatBits,
6715 bool isBigEndian) const {
6716 EVT VT = getValueType(0);
6717 assert(VT.isVector() && "Expected a vector type");
6718 unsigned sz = VT.getSizeInBits();
6719 if (MinSplatBits > sz)
6722 SplatValue = APInt(sz, 0);
6723 SplatUndef = APInt(sz, 0);
6725 // Get the bits. Bits with undefined values (when the corresponding element
6726 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6727 // in SplatValue. If any of the values are not constant, give up and return
6729 unsigned int nOps = getNumOperands();
6730 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6731 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6733 for (unsigned j = 0; j < nOps; ++j) {
6734 unsigned i = isBigEndian ? nOps-1-j : j;
6735 SDValue OpVal = getOperand(i);
6736 unsigned BitPos = j * EltBitSize;
6738 if (OpVal.getOpcode() == ISD::UNDEF)
6739 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6740 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6741 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6742 zextOrTrunc(sz) << BitPos;
6743 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6744 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6749 // The build_vector is all constants or undefs. Find the smallest element
6750 // size that splats the vector.
6752 HasAnyUndefs = (SplatUndef != 0);
6755 unsigned HalfSize = sz / 2;
6756 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6757 APInt LowValue = SplatValue.trunc(HalfSize);
6758 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6759 APInt LowUndef = SplatUndef.trunc(HalfSize);
6761 // If the two halves do not match (ignoring undef bits), stop here.
6762 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6763 MinSplatBits > HalfSize)
6766 SplatValue = HighValue | LowValue;
6767 SplatUndef = HighUndef & LowUndef;
6776 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6777 if (UndefElements) {
6778 UndefElements->clear();
6779 UndefElements->resize(getNumOperands());
6782 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6783 SDValue Op = getOperand(i);
6784 if (Op.getOpcode() == ISD::UNDEF) {
6786 (*UndefElements)[i] = true;
6787 } else if (!Splatted) {
6789 } else if (Splatted != Op) {
6795 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6796 "Can only have a splat without a constant for all undefs.");
6797 return getOperand(0);
6804 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6805 return dyn_cast_or_null<ConstantSDNode>(
6806 getSplatValue(UndefElements).getNode());
6810 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6811 return dyn_cast_or_null<ConstantFPSDNode>(
6812 getSplatValue(UndefElements).getNode());
6815 bool BuildVectorSDNode::isConstant() const {
6816 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6817 unsigned Opc = getOperand(i).getOpcode();
6818 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6824 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6825 // Find the first non-undef value in the shuffle mask.
6827 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6830 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6832 // Make sure all remaining elements are either undef or the same as the first
6834 for (int Idx = Mask[i]; i != e; ++i)
6835 if (Mask[i] >= 0 && Mask[i] != Idx)
6841 static void checkForCyclesHelper(const SDNode *N,
6842 SmallPtrSetImpl<const SDNode*> &Visited,
6843 SmallPtrSetImpl<const SDNode*> &Checked,
6844 const llvm::SelectionDAG *DAG) {
6845 // If this node has already been checked, don't check it again.
6846 if (Checked.count(N))
6849 // If a node has already been visited on this depth-first walk, reject it as
6851 if (!Visited.insert(N).second) {
6852 errs() << "Detected cycle in SelectionDAG\n";
6853 dbgs() << "Offending node:\n";
6854 N->dumprFull(DAG); dbgs() << "\n";
6858 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6859 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6866 void llvm::checkForCycles(const llvm::SDNode *N,
6867 const llvm::SelectionDAG *DAG,
6875 assert(N && "Checking nonexistent SDNode");
6876 SmallPtrSet<const SDNode*, 32> visited;
6877 SmallPtrSet<const SDNode*, 32> checked;
6878 checkForCyclesHelper(N, visited, checked, DAG);
6883 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6884 checkForCycles(DAG->getRoot().getNode(), DAG, force);