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