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 ShuffleVectorSDNode::commuteMask(M);
1452 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1453 SDValue N2, const int *Mask) {
1454 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1455 "Invalid VECTOR_SHUFFLE");
1457 // Canonicalize shuffle undef, undef -> undef
1458 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1459 return getUNDEF(VT);
1461 // Validate that all indices in Mask are within the range of the elements
1462 // input to the shuffle.
1463 unsigned NElts = VT.getVectorNumElements();
1464 SmallVector<int, 8> MaskVec;
1465 for (unsigned i = 0; i != NElts; ++i) {
1466 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1467 MaskVec.push_back(Mask[i]);
1470 // Canonicalize shuffle v, v -> v, undef
1473 for (unsigned i = 0; i != NElts; ++i)
1474 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1477 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1478 if (N1.getOpcode() == ISD::UNDEF)
1479 commuteShuffle(N1, N2, MaskVec);
1481 // If shuffling a splat, try to blend the splat instead. We do this here so
1482 // that even when this arises during lowering we don't have to re-handle it.
1483 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1484 BitVector UndefElements;
1485 SDValue Splat = BV->getSplatValue(&UndefElements);
1489 for (int i = 0; i < (int)NElts; ++i) {
1490 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1493 // If this input comes from undef, mark it as such.
1494 if (UndefElements[MaskVec[i] - Offset]) {
1499 // If we can blend a non-undef lane, use that instead.
1500 if (!UndefElements[i])
1501 MaskVec[i] = i + Offset;
1504 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1505 BlendSplat(N1BV, 0);
1506 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1507 BlendSplat(N2BV, NElts);
1509 // Canonicalize all index into lhs, -> shuffle lhs, undef
1510 // Canonicalize all index into rhs, -> shuffle rhs, undef
1511 bool AllLHS = true, AllRHS = true;
1512 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1513 for (unsigned i = 0; i != NElts; ++i) {
1514 if (MaskVec[i] >= (int)NElts) {
1519 } else if (MaskVec[i] >= 0) {
1523 if (AllLHS && AllRHS)
1524 return getUNDEF(VT);
1525 if (AllLHS && !N2Undef)
1529 commuteShuffle(N1, N2, MaskVec);
1531 // Reset our undef status after accounting for the mask.
1532 N2Undef = N2.getOpcode() == ISD::UNDEF;
1533 // Re-check whether both sides ended up undef.
1534 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1535 return getUNDEF(VT);
1537 // If Identity shuffle return that node.
1538 bool Identity = true, AllSame = true;
1539 for (unsigned i = 0; i != NElts; ++i) {
1540 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1541 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1543 if (Identity && NElts)
1546 // Shuffling a constant splat doesn't change the result.
1550 // Look through any bitcasts. We check that these don't change the number
1551 // (and size) of elements and just changes their types.
1552 while (V.getOpcode() == ISD::BITCAST)
1553 V = V->getOperand(0);
1555 // A splat should always show up as a build vector node.
1556 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1557 BitVector UndefElements;
1558 SDValue Splat = BV->getSplatValue(&UndefElements);
1559 // If this is a splat of an undef, shuffling it is also undef.
1560 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1561 return getUNDEF(VT);
1564 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1566 // We only have a splat which can skip shuffles if there is a splatted
1567 // value and no undef lanes rearranged by the shuffle.
1568 if (Splat && UndefElements.none()) {
1569 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1570 // number of elements match or the value splatted is a zero constant.
1573 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1574 if (C->isNullValue())
1578 // If the shuffle itself creates a splat, build the vector directly.
1579 if (AllSame && SameNumElts) {
1580 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1581 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1583 EVT BuildVT = BV->getValueType(0);
1584 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1586 // We may have jumped through bitcasts, so the type of the
1587 // BUILD_VECTOR may not match the type of the shuffle.
1589 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1595 FoldingSetNodeID ID;
1596 SDValue Ops[2] = { N1, N2 };
1597 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1598 for (unsigned i = 0; i != NElts; ++i)
1599 ID.AddInteger(MaskVec[i]);
1602 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1603 return SDValue(E, 0);
1605 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1606 // SDNode doesn't have access to it. This memory will be "leaked" when
1607 // the node is deallocated, but recovered when the NodeAllocator is released.
1608 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1609 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1611 ShuffleVectorSDNode *N =
1612 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1613 dl.getDebugLoc(), N1, N2,
1615 CSEMap.InsertNode(N, IP);
1617 return SDValue(N, 0);
1620 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1621 MVT VT = SV.getSimpleValueType(0);
1622 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1623 ShuffleVectorSDNode::commuteMask(MaskVec);
1625 SDValue Op0 = SV.getOperand(0);
1626 SDValue Op1 = SV.getOperand(1);
1627 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1630 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1631 SDValue Val, SDValue DTy,
1632 SDValue STy, SDValue Rnd, SDValue Sat,
1633 ISD::CvtCode Code) {
1634 // If the src and dest types are the same and the conversion is between
1635 // integer types of the same sign or two floats, no conversion is necessary.
1637 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1640 FoldingSetNodeID ID;
1641 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1642 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1644 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1645 return SDValue(E, 0);
1647 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1650 CSEMap.InsertNode(N, IP);
1652 return SDValue(N, 0);
1655 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1656 FoldingSetNodeID ID;
1657 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1658 ID.AddInteger(RegNo);
1660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1661 return SDValue(E, 0);
1663 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1664 CSEMap.InsertNode(N, IP);
1666 return SDValue(N, 0);
1669 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1670 FoldingSetNodeID ID;
1671 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1672 ID.AddPointer(RegMask);
1674 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1675 return SDValue(E, 0);
1677 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1678 CSEMap.InsertNode(N, IP);
1680 return SDValue(N, 0);
1683 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1684 FoldingSetNodeID ID;
1685 SDValue Ops[] = { Root };
1686 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1687 ID.AddPointer(Label);
1689 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1690 return SDValue(E, 0);
1692 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1693 dl.getDebugLoc(), Root, Label);
1694 CSEMap.InsertNode(N, IP);
1696 return SDValue(N, 0);
1700 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1703 unsigned char TargetFlags) {
1704 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1706 FoldingSetNodeID ID;
1707 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1709 ID.AddInteger(Offset);
1710 ID.AddInteger(TargetFlags);
1712 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1713 return SDValue(E, 0);
1715 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1717 CSEMap.InsertNode(N, IP);
1719 return SDValue(N, 0);
1722 SDValue SelectionDAG::getSrcValue(const Value *V) {
1723 assert((!V || V->getType()->isPointerTy()) &&
1724 "SrcValue is not a pointer?");
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1731 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1732 return SDValue(E, 0);
1734 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1735 CSEMap.InsertNode(N, IP);
1737 return SDValue(N, 0);
1740 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1741 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1742 FoldingSetNodeID ID;
1743 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1747 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1748 return SDValue(E, 0);
1750 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1751 CSEMap.InsertNode(N, IP);
1753 return SDValue(N, 0);
1756 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1757 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1758 unsigned SrcAS, unsigned DestAS) {
1759 SDValue Ops[] = {Ptr};
1760 FoldingSetNodeID ID;
1761 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1762 ID.AddInteger(SrcAS);
1763 ID.AddInteger(DestAS);
1766 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1767 return SDValue(E, 0);
1769 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1771 VT, Ptr, SrcAS, DestAS);
1772 CSEMap.InsertNode(N, IP);
1774 return SDValue(N, 0);
1777 /// getShiftAmountOperand - Return the specified value casted to
1778 /// the target's desired shift amount type.
1779 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1780 EVT OpTy = Op.getValueType();
1781 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1782 if (OpTy == ShTy || OpTy.isVector()) return Op;
1784 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1785 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1788 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1789 /// specified value type.
1790 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1791 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1792 unsigned ByteSize = VT.getStoreSize();
1793 Type *Ty = VT.getTypeForEVT(*getContext());
1794 unsigned StackAlign =
1795 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1797 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1798 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1801 /// CreateStackTemporary - Create a stack temporary suitable for holding
1802 /// either of the specified value types.
1803 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1804 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1805 VT2.getStoreSizeInBits())/8;
1806 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1807 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1808 const DataLayout *TD = TLI->getDataLayout();
1809 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1810 TD->getPrefTypeAlignment(Ty2));
1812 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1813 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1814 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1817 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1818 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1819 // These setcc operations always fold.
1823 case ISD::SETFALSE2: return getConstant(0, VT);
1825 case ISD::SETTRUE2: {
1826 TargetLowering::BooleanContent Cnt =
1827 TLI->getBooleanContents(N1->getValueType(0));
1829 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1842 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1846 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1847 const APInt &C2 = N2C->getAPIntValue();
1848 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1849 const APInt &C1 = N1C->getAPIntValue();
1852 default: llvm_unreachable("Unknown integer setcc!");
1853 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1854 case ISD::SETNE: return getConstant(C1 != C2, VT);
1855 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1856 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1857 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1858 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1859 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1860 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1861 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1862 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1866 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1867 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1868 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1871 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1872 return getUNDEF(VT);
1874 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1875 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1876 return getUNDEF(VT);
1878 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1879 R==APFloat::cmpLessThan, VT);
1880 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1881 return getUNDEF(VT);
1883 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1884 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1885 return getUNDEF(VT);
1887 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1888 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1889 return getUNDEF(VT);
1891 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1892 R==APFloat::cmpEqual, VT);
1893 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1894 return getUNDEF(VT);
1896 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1897 R==APFloat::cmpEqual, VT);
1898 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1899 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1900 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1901 R==APFloat::cmpEqual, VT);
1902 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1903 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1904 R==APFloat::cmpLessThan, VT);
1905 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1906 R==APFloat::cmpUnordered, VT);
1907 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1908 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1911 // Ensure that the constant occurs on the RHS.
1912 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1913 MVT CompVT = N1.getValueType().getSimpleVT();
1914 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1917 return getSetCC(dl, VT, N2, N1, SwappedCond);
1921 // Could not fold it.
1925 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1926 /// use this predicate to simplify operations downstream.
1927 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1928 // This predicate is not safe for vector operations.
1929 if (Op.getValueType().isVector())
1932 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1933 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1936 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1937 /// this predicate to simplify operations downstream. Mask is known to be zero
1938 /// for bits that V cannot have.
1939 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1940 unsigned Depth) const {
1941 APInt KnownZero, KnownOne;
1942 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1943 return (KnownZero & Mask) == Mask;
1946 /// Determine which bits of Op are known to be either zero or one and return
1947 /// them in the KnownZero/KnownOne bitsets.
1948 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1949 APInt &KnownOne, unsigned Depth) const {
1950 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1952 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1954 return; // Limit search depth.
1956 APInt KnownZero2, KnownOne2;
1958 switch (Op.getOpcode()) {
1960 // We know all of the bits for a constant!
1961 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1962 KnownZero = ~KnownOne;
1965 // If either the LHS or the RHS are Zero, the result is zero.
1966 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1967 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1969 // Output known-1 bits are only known if set in both the LHS & RHS.
1970 KnownOne &= KnownOne2;
1971 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1972 KnownZero |= KnownZero2;
1975 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1976 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1978 // Output known-0 bits are only known if clear in both the LHS & RHS.
1979 KnownZero &= KnownZero2;
1980 // Output known-1 are known to be set if set in either the LHS | RHS.
1981 KnownOne |= KnownOne2;
1984 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1985 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1987 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1988 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1989 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1990 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1991 KnownZero = KnownZeroOut;
1995 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1996 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1998 // If low bits are zero in either operand, output low known-0 bits.
1999 // Also compute a conserative estimate for high known-0 bits.
2000 // More trickiness is possible, but this is sufficient for the
2001 // interesting case of alignment computation.
2002 KnownOne.clearAllBits();
2003 unsigned TrailZ = KnownZero.countTrailingOnes() +
2004 KnownZero2.countTrailingOnes();
2005 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2006 KnownZero2.countLeadingOnes(),
2007 BitWidth) - BitWidth;
2009 TrailZ = std::min(TrailZ, BitWidth);
2010 LeadZ = std::min(LeadZ, BitWidth);
2011 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2012 APInt::getHighBitsSet(BitWidth, LeadZ);
2016 // For the purposes of computing leading zeros we can conservatively
2017 // treat a udiv as a logical right shift by the power of 2 known to
2018 // be less than the denominator.
2019 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2020 unsigned LeadZ = KnownZero2.countLeadingOnes();
2022 KnownOne2.clearAllBits();
2023 KnownZero2.clearAllBits();
2024 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2025 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2026 if (RHSUnknownLeadingOnes != BitWidth)
2027 LeadZ = std::min(BitWidth,
2028 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2030 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2034 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2035 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2037 // Only known if known in both the LHS and RHS.
2038 KnownOne &= KnownOne2;
2039 KnownZero &= KnownZero2;
2041 case ISD::SELECT_CC:
2042 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2043 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2045 // Only known if known in both the LHS and RHS.
2046 KnownOne &= KnownOne2;
2047 KnownZero &= KnownZero2;
2055 if (Op.getResNo() != 1)
2057 // The boolean result conforms to getBooleanContents.
2058 // If we know the result of a setcc has the top bits zero, use this info.
2059 // We know that we have an integer-based boolean since these operations
2060 // are only available for integer.
2061 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2062 TargetLowering::ZeroOrOneBooleanContent &&
2064 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2067 // If we know the result of a setcc has the top bits zero, use this info.
2068 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2069 TargetLowering::ZeroOrOneBooleanContent &&
2071 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2074 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2075 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2076 unsigned ShAmt = SA->getZExtValue();
2078 // If the shift count is an invalid immediate, don't do anything.
2079 if (ShAmt >= BitWidth)
2082 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2083 KnownZero <<= ShAmt;
2085 // low bits known zero.
2086 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2090 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2091 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2092 unsigned ShAmt = SA->getZExtValue();
2094 // If the shift count is an invalid immediate, don't do anything.
2095 if (ShAmt >= BitWidth)
2098 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2099 KnownZero = KnownZero.lshr(ShAmt);
2100 KnownOne = KnownOne.lshr(ShAmt);
2102 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2103 KnownZero |= HighBits; // High bits known zero.
2107 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2108 unsigned ShAmt = SA->getZExtValue();
2110 // If the shift count is an invalid immediate, don't do anything.
2111 if (ShAmt >= BitWidth)
2114 // If any of the demanded bits are produced by the sign extension, we also
2115 // demand the input sign bit.
2116 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2118 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2119 KnownZero = KnownZero.lshr(ShAmt);
2120 KnownOne = KnownOne.lshr(ShAmt);
2122 // Handle the sign bits.
2123 APInt SignBit = APInt::getSignBit(BitWidth);
2124 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2126 if (KnownZero.intersects(SignBit)) {
2127 KnownZero |= HighBits; // New bits are known zero.
2128 } else if (KnownOne.intersects(SignBit)) {
2129 KnownOne |= HighBits; // New bits are known one.
2133 case ISD::SIGN_EXTEND_INREG: {
2134 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2135 unsigned EBits = EVT.getScalarType().getSizeInBits();
2137 // Sign extension. Compute the demanded bits in the result that are not
2138 // present in the input.
2139 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2141 APInt InSignBit = APInt::getSignBit(EBits);
2142 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2144 // If the sign extended bits are demanded, we know that the sign
2146 InSignBit = InSignBit.zext(BitWidth);
2147 if (NewBits.getBoolValue())
2148 InputDemandedBits |= InSignBit;
2150 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2151 KnownOne &= InputDemandedBits;
2152 KnownZero &= InputDemandedBits;
2154 // If the sign bit of the input is known set or clear, then we know the
2155 // top bits of the result.
2156 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2157 KnownZero |= NewBits;
2158 KnownOne &= ~NewBits;
2159 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2160 KnownOne |= NewBits;
2161 KnownZero &= ~NewBits;
2162 } else { // Input sign bit unknown
2163 KnownZero &= ~NewBits;
2164 KnownOne &= ~NewBits;
2169 case ISD::CTTZ_ZERO_UNDEF:
2171 case ISD::CTLZ_ZERO_UNDEF:
2173 unsigned LowBits = Log2_32(BitWidth)+1;
2174 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2175 KnownOne.clearAllBits();
2179 LoadSDNode *LD = cast<LoadSDNode>(Op);
2180 // If this is a ZEXTLoad and we are looking at the loaded value.
2181 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2182 EVT VT = LD->getMemoryVT();
2183 unsigned MemBits = VT.getScalarType().getSizeInBits();
2184 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2185 } else if (const MDNode *Ranges = LD->getRanges()) {
2186 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2190 case ISD::ZERO_EXTEND: {
2191 EVT InVT = Op.getOperand(0).getValueType();
2192 unsigned InBits = InVT.getScalarType().getSizeInBits();
2193 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2194 KnownZero = KnownZero.trunc(InBits);
2195 KnownOne = KnownOne.trunc(InBits);
2196 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2197 KnownZero = KnownZero.zext(BitWidth);
2198 KnownOne = KnownOne.zext(BitWidth);
2199 KnownZero |= NewBits;
2202 case ISD::SIGN_EXTEND: {
2203 EVT InVT = Op.getOperand(0).getValueType();
2204 unsigned InBits = InVT.getScalarType().getSizeInBits();
2205 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2207 KnownZero = KnownZero.trunc(InBits);
2208 KnownOne = KnownOne.trunc(InBits);
2209 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2211 // Note if the sign bit is known to be zero or one.
2212 bool SignBitKnownZero = KnownZero.isNegative();
2213 bool SignBitKnownOne = KnownOne.isNegative();
2215 KnownZero = KnownZero.zext(BitWidth);
2216 KnownOne = KnownOne.zext(BitWidth);
2218 // If the sign bit is known zero or one, the top bits match.
2219 if (SignBitKnownZero)
2220 KnownZero |= NewBits;
2221 else if (SignBitKnownOne)
2222 KnownOne |= NewBits;
2225 case ISD::ANY_EXTEND: {
2226 EVT InVT = Op.getOperand(0).getValueType();
2227 unsigned InBits = InVT.getScalarType().getSizeInBits();
2228 KnownZero = KnownZero.trunc(InBits);
2229 KnownOne = KnownOne.trunc(InBits);
2230 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2231 KnownZero = KnownZero.zext(BitWidth);
2232 KnownOne = KnownOne.zext(BitWidth);
2235 case ISD::TRUNCATE: {
2236 EVT InVT = Op.getOperand(0).getValueType();
2237 unsigned InBits = InVT.getScalarType().getSizeInBits();
2238 KnownZero = KnownZero.zext(InBits);
2239 KnownOne = KnownOne.zext(InBits);
2240 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2241 KnownZero = KnownZero.trunc(BitWidth);
2242 KnownOne = KnownOne.trunc(BitWidth);
2245 case ISD::AssertZext: {
2246 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2247 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2248 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2249 KnownZero |= (~InMask);
2250 KnownOne &= (~KnownZero);
2254 // All bits are zero except the low bit.
2255 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2259 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2260 // We know that the top bits of C-X are clear if X contains less bits
2261 // than C (i.e. no wrap-around can happen). For example, 20-X is
2262 // positive if we can prove that X is >= 0 and < 16.
2263 if (CLHS->getAPIntValue().isNonNegative()) {
2264 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2265 // NLZ can't be BitWidth with no sign bit
2266 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2267 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2269 // If all of the MaskV bits are known to be zero, then we know the
2270 // output top bits are zero, because we now know that the output is
2272 if ((KnownZero2 & MaskV) == MaskV) {
2273 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2274 // Top bits known zero.
2275 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2283 // Output known-0 bits are known if clear or set in both the low clear bits
2284 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2285 // low 3 bits clear.
2286 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2287 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2289 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2290 KnownZeroOut = std::min(KnownZeroOut,
2291 KnownZero2.countTrailingOnes());
2293 if (Op.getOpcode() == ISD::ADD) {
2294 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2298 // With ADDE, a carry bit may be added in, so we can only use this
2299 // information if we know (at least) that the low two bits are clear. We
2300 // then return to the caller that the low bit is unknown but that other bits
2302 if (KnownZeroOut >= 2) // ADDE
2303 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2307 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2308 const APInt &RA = Rem->getAPIntValue().abs();
2309 if (RA.isPowerOf2()) {
2310 APInt LowBits = RA - 1;
2311 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2313 // The low bits of the first operand are unchanged by the srem.
2314 KnownZero = KnownZero2 & LowBits;
2315 KnownOne = KnownOne2 & LowBits;
2317 // If the first operand is non-negative or has all low bits zero, then
2318 // the upper bits are all zero.
2319 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2320 KnownZero |= ~LowBits;
2322 // If the first operand is negative and not all low bits are zero, then
2323 // the upper bits are all one.
2324 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2325 KnownOne |= ~LowBits;
2326 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2331 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2332 const APInt &RA = Rem->getAPIntValue();
2333 if (RA.isPowerOf2()) {
2334 APInt LowBits = (RA - 1);
2335 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2337 // The upper bits are all zero, the lower ones are unchanged.
2338 KnownZero = KnownZero2 | ~LowBits;
2339 KnownOne = KnownOne2 & LowBits;
2344 // Since the result is less than or equal to either operand, any leading
2345 // zero bits in either operand must also exist in the result.
2346 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2347 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2349 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2350 KnownZero2.countLeadingOnes());
2351 KnownOne.clearAllBits();
2352 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2355 case ISD::EXTRACT_ELEMENT: {
2356 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2357 const unsigned Index =
2358 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2359 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2361 // Remove low part of known bits mask
2362 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2363 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2365 // Remove high part of known bit mask
2366 KnownZero = KnownZero.trunc(BitWidth);
2367 KnownOne = KnownOne.trunc(BitWidth);
2370 case ISD::FrameIndex:
2371 case ISD::TargetFrameIndex:
2372 if (unsigned Align = InferPtrAlignment(Op)) {
2373 // The low bits are known zero if the pointer is aligned.
2374 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2380 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2383 case ISD::INTRINSIC_WO_CHAIN:
2384 case ISD::INTRINSIC_W_CHAIN:
2385 case ISD::INTRINSIC_VOID:
2386 // Allow the target to implement this method for its nodes.
2387 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2391 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2394 /// ComputeNumSignBits - Return the number of times the sign bit of the
2395 /// register is replicated into the other bits. We know that at least 1 bit
2396 /// is always equal to the sign bit (itself), but other cases can give us
2397 /// information. For example, immediately after an "SRA X, 2", we know that
2398 /// the top 3 bits are all equal to each other, so we return 3.
2399 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2400 EVT VT = Op.getValueType();
2401 assert(VT.isInteger() && "Invalid VT!");
2402 unsigned VTBits = VT.getScalarType().getSizeInBits();
2404 unsigned FirstAnswer = 1;
2407 return 1; // Limit search depth.
2409 switch (Op.getOpcode()) {
2411 case ISD::AssertSext:
2412 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2413 return VTBits-Tmp+1;
2414 case ISD::AssertZext:
2415 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2418 case ISD::Constant: {
2419 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2420 return Val.getNumSignBits();
2423 case ISD::SIGN_EXTEND:
2425 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2426 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2428 case ISD::SIGN_EXTEND_INREG:
2429 // Max of the input and what this extends.
2431 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2434 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2435 return std::max(Tmp, Tmp2);
2438 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2439 // SRA X, C -> adds C sign bits.
2440 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2441 Tmp += C->getZExtValue();
2442 if (Tmp > VTBits) Tmp = VTBits;
2446 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2447 // shl destroys sign bits.
2448 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2449 if (C->getZExtValue() >= VTBits || // Bad shift.
2450 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2451 return Tmp - C->getZExtValue();
2456 case ISD::XOR: // NOT is handled here.
2457 // Logical binary ops preserve the number of sign bits at the worst.
2458 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2460 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2461 FirstAnswer = std::min(Tmp, Tmp2);
2462 // We computed what we know about the sign bits as our first
2463 // answer. Now proceed to the generic code that uses
2464 // computeKnownBits, and pick whichever answer is better.
2469 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2470 if (Tmp == 1) return 1; // Early out.
2471 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2472 return std::min(Tmp, Tmp2);
2480 if (Op.getResNo() != 1)
2482 // The boolean result conforms to getBooleanContents. Fall through.
2483 // If setcc returns 0/-1, all bits are sign bits.
2484 // We know that we have an integer-based boolean since these operations
2485 // are only available for integer.
2486 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2487 TargetLowering::ZeroOrNegativeOneBooleanContent)
2491 // If setcc returns 0/-1, all bits are sign bits.
2492 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2493 TargetLowering::ZeroOrNegativeOneBooleanContent)
2498 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2499 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2501 // Handle rotate right by N like a rotate left by 32-N.
2502 if (Op.getOpcode() == ISD::ROTR)
2503 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2505 // If we aren't rotating out all of the known-in sign bits, return the
2506 // number that are left. This handles rotl(sext(x), 1) for example.
2507 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2508 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2512 // Add can have at most one carry bit. Thus we know that the output
2513 // is, at worst, one more bit than the inputs.
2514 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2515 if (Tmp == 1) return 1; // Early out.
2517 // Special case decrementing a value (ADD X, -1):
2518 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2519 if (CRHS->isAllOnesValue()) {
2520 APInt KnownZero, KnownOne;
2521 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2523 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2525 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2528 // If we are subtracting one from a positive number, there is no carry
2529 // out of the result.
2530 if (KnownZero.isNegative())
2534 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2535 if (Tmp2 == 1) return 1;
2536 return std::min(Tmp, Tmp2)-1;
2539 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2540 if (Tmp2 == 1) return 1;
2543 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2544 if (CLHS->isNullValue()) {
2545 APInt KnownZero, KnownOne;
2546 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2547 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2549 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2552 // If the input is known to be positive (the sign bit is known clear),
2553 // the output of the NEG has the same number of sign bits as the input.
2554 if (KnownZero.isNegative())
2557 // Otherwise, we treat this like a SUB.
2560 // Sub can have at most one carry bit. Thus we know that the output
2561 // is, at worst, one more bit than the inputs.
2562 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2563 if (Tmp == 1) return 1; // Early out.
2564 return std::min(Tmp, Tmp2)-1;
2566 // FIXME: it's tricky to do anything useful for this, but it is an important
2567 // case for targets like X86.
2569 case ISD::EXTRACT_ELEMENT: {
2570 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2571 const int BitWidth = Op.getValueType().getSizeInBits();
2573 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2575 // Get reverse index (starting from 1), Op1 value indexes elements from
2576 // little end. Sign starts at big end.
2577 const int rIndex = Items - 1 -
2578 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2580 // If the sign portion ends in our element the substraction gives correct
2581 // result. Otherwise it gives either negative or > bitwidth result
2582 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2586 // If we are looking at the loaded value of the SDNode.
2587 if (Op.getResNo() == 0) {
2588 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2589 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2590 unsigned ExtType = LD->getExtensionType();
2593 case ISD::SEXTLOAD: // '17' bits known
2594 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2595 return VTBits-Tmp+1;
2596 case ISD::ZEXTLOAD: // '16' bits known
2597 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2603 // Allow the target to implement this method for its nodes.
2604 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2605 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2606 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2607 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2608 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2609 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2612 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2613 // use this information.
2614 APInt KnownZero, KnownOne;
2615 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2618 if (KnownZero.isNegative()) { // sign bit is 0
2620 } else if (KnownOne.isNegative()) { // sign bit is 1;
2627 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2628 // the number of identical bits in the top of the input value.
2630 Mask <<= Mask.getBitWidth()-VTBits;
2631 // Return # leading zeros. We use 'min' here in case Val was zero before
2632 // shifting. We don't want to return '64' as for an i32 "0".
2633 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2636 /// isBaseWithConstantOffset - Return true if the specified operand is an
2637 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2638 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2639 /// semantics as an ADD. This handles the equivalence:
2640 /// X|Cst == X+Cst iff X&Cst = 0.
2641 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2642 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2643 !isa<ConstantSDNode>(Op.getOperand(1)))
2646 if (Op.getOpcode() == ISD::OR &&
2647 !MaskedValueIsZero(Op.getOperand(0),
2648 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2655 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2656 // If we're told that NaNs won't happen, assume they won't.
2657 if (getTarget().Options.NoNaNsFPMath)
2660 // If the value is a constant, we can obviously see if it is a NaN or not.
2661 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2662 return !C->getValueAPF().isNaN();
2664 // TODO: Recognize more cases here.
2669 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2670 // If the value is a constant, we can obviously see if it is a zero or not.
2671 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2672 return !C->isZero();
2674 // TODO: Recognize more cases here.
2675 switch (Op.getOpcode()) {
2678 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2679 return !C->isNullValue();
2686 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2687 // Check the obvious case.
2688 if (A == B) return true;
2690 // For for negative and positive zero.
2691 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2692 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2693 if (CA->isZero() && CB->isZero()) return true;
2695 // Otherwise they may not be equal.
2699 /// getNode - Gets or creates the specified node.
2701 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2702 FoldingSetNodeID ID;
2703 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2705 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2706 return SDValue(E, 0);
2708 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2709 DL.getDebugLoc(), getVTList(VT));
2710 CSEMap.InsertNode(N, IP);
2713 return SDValue(N, 0);
2716 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2717 EVT VT, SDValue Operand) {
2718 // Constant fold unary operations with an integer constant operand. Even
2719 // opaque constant will be folded, because the folding of unary operations
2720 // doesn't create new constants with different values. Nevertheless, the
2721 // opaque flag is preserved during folding to prevent future folding with
2723 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2724 const APInt &Val = C->getAPIntValue();
2727 case ISD::SIGN_EXTEND:
2728 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2729 C->isTargetOpcode(), C->isOpaque());
2730 case ISD::ANY_EXTEND:
2731 case ISD::ZERO_EXTEND:
2733 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2734 C->isTargetOpcode(), C->isOpaque());
2735 case ISD::UINT_TO_FP:
2736 case ISD::SINT_TO_FP: {
2737 APFloat apf(EVTToAPFloatSemantics(VT),
2738 APInt::getNullValue(VT.getSizeInBits()));
2739 (void)apf.convertFromAPInt(Val,
2740 Opcode==ISD::SINT_TO_FP,
2741 APFloat::rmNearestTiesToEven);
2742 return getConstantFP(apf, VT);
2745 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2746 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2747 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2748 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2749 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2750 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2753 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2756 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2759 case ISD::CTLZ_ZERO_UNDEF:
2760 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2763 case ISD::CTTZ_ZERO_UNDEF:
2764 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2769 // Constant fold unary operations with a floating point constant operand.
2770 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2771 APFloat V = C->getValueAPF(); // make copy
2775 return getConstantFP(V, VT);
2778 return getConstantFP(V, VT);
2780 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2781 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2782 return getConstantFP(V, VT);
2786 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2787 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2788 return getConstantFP(V, VT);
2792 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2793 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2794 return getConstantFP(V, VT);
2797 case ISD::FP_EXTEND: {
2799 // This can return overflow, underflow, or inexact; we don't care.
2800 // FIXME need to be more flexible about rounding mode.
2801 (void)V.convert(EVTToAPFloatSemantics(VT),
2802 APFloat::rmNearestTiesToEven, &ignored);
2803 return getConstantFP(V, VT);
2805 case ISD::FP_TO_SINT:
2806 case ISD::FP_TO_UINT: {
2809 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2810 // FIXME need to be more flexible about rounding mode.
2811 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2812 Opcode==ISD::FP_TO_SINT,
2813 APFloat::rmTowardZero, &ignored);
2814 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2816 APInt api(VT.getSizeInBits(), x);
2817 return getConstant(api, VT);
2820 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2821 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2822 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2823 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2824 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2825 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2830 // Constant fold unary operations with a vector integer operand.
2831 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2832 if (BV->isConstant()) {
2835 // FIXME: Entirely reasonable to perform folding of other unary
2836 // operations here as the need arises.
2838 case ISD::UINT_TO_FP:
2839 case ISD::SINT_TO_FP: {
2840 // Let the above scalar folding handle the folding of each element.
2841 SmallVector<SDValue, 8> Ops;
2842 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2843 SDValue OpN = BV->getOperand(i);
2844 OpN = getNode(Opcode, DL, VT.getVectorElementType(), OpN);
2847 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2853 unsigned OpOpcode = Operand.getNode()->getOpcode();
2855 case ISD::TokenFactor:
2856 case ISD::MERGE_VALUES:
2857 case ISD::CONCAT_VECTORS:
2858 return Operand; // Factor, merge or concat of one node? No need.
2859 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2860 case ISD::FP_EXTEND:
2861 assert(VT.isFloatingPoint() &&
2862 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2863 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2864 assert((!VT.isVector() ||
2865 VT.getVectorNumElements() ==
2866 Operand.getValueType().getVectorNumElements()) &&
2867 "Vector element count mismatch!");
2868 if (Operand.getOpcode() == ISD::UNDEF)
2869 return getUNDEF(VT);
2871 case ISD::SIGN_EXTEND:
2872 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2873 "Invalid SIGN_EXTEND!");
2874 if (Operand.getValueType() == VT) return Operand; // noop extension
2875 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2876 "Invalid sext node, dst < src!");
2877 assert((!VT.isVector() ||
2878 VT.getVectorNumElements() ==
2879 Operand.getValueType().getVectorNumElements()) &&
2880 "Vector element count mismatch!");
2881 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2882 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2883 else if (OpOpcode == ISD::UNDEF)
2884 // sext(undef) = 0, because the top bits will all be the same.
2885 return getConstant(0, VT);
2887 case ISD::ZERO_EXTEND:
2888 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2889 "Invalid ZERO_EXTEND!");
2890 if (Operand.getValueType() == VT) return Operand; // noop extension
2891 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2892 "Invalid zext node, dst < src!");
2893 assert((!VT.isVector() ||
2894 VT.getVectorNumElements() ==
2895 Operand.getValueType().getVectorNumElements()) &&
2896 "Vector element count mismatch!");
2897 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2898 return getNode(ISD::ZERO_EXTEND, DL, VT,
2899 Operand.getNode()->getOperand(0));
2900 else if (OpOpcode == ISD::UNDEF)
2901 // zext(undef) = 0, because the top bits will be zero.
2902 return getConstant(0, VT);
2904 case ISD::ANY_EXTEND:
2905 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2906 "Invalid ANY_EXTEND!");
2907 if (Operand.getValueType() == VT) return Operand; // noop extension
2908 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2909 "Invalid anyext node, dst < src!");
2910 assert((!VT.isVector() ||
2911 VT.getVectorNumElements() ==
2912 Operand.getValueType().getVectorNumElements()) &&
2913 "Vector element count mismatch!");
2915 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2916 OpOpcode == ISD::ANY_EXTEND)
2917 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2918 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2919 else if (OpOpcode == ISD::UNDEF)
2920 return getUNDEF(VT);
2922 // (ext (trunx x)) -> x
2923 if (OpOpcode == ISD::TRUNCATE) {
2924 SDValue OpOp = Operand.getNode()->getOperand(0);
2925 if (OpOp.getValueType() == VT)
2930 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2931 "Invalid TRUNCATE!");
2932 if (Operand.getValueType() == VT) return Operand; // noop truncate
2933 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2934 "Invalid truncate node, src < dst!");
2935 assert((!VT.isVector() ||
2936 VT.getVectorNumElements() ==
2937 Operand.getValueType().getVectorNumElements()) &&
2938 "Vector element count mismatch!");
2939 if (OpOpcode == ISD::TRUNCATE)
2940 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2941 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2942 OpOpcode == ISD::ANY_EXTEND) {
2943 // If the source is smaller than the dest, we still need an extend.
2944 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2945 .bitsLT(VT.getScalarType()))
2946 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2947 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2948 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2949 return Operand.getNode()->getOperand(0);
2951 if (OpOpcode == ISD::UNDEF)
2952 return getUNDEF(VT);
2955 // Basic sanity checking.
2956 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2957 && "Cannot BITCAST between types of different sizes!");
2958 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2959 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2960 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2961 if (OpOpcode == ISD::UNDEF)
2962 return getUNDEF(VT);
2964 case ISD::SCALAR_TO_VECTOR:
2965 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2966 (VT.getVectorElementType() == Operand.getValueType() ||
2967 (VT.getVectorElementType().isInteger() &&
2968 Operand.getValueType().isInteger() &&
2969 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2970 "Illegal SCALAR_TO_VECTOR node!");
2971 if (OpOpcode == ISD::UNDEF)
2972 return getUNDEF(VT);
2973 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2974 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2975 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2976 Operand.getConstantOperandVal(1) == 0 &&
2977 Operand.getOperand(0).getValueType() == VT)
2978 return Operand.getOperand(0);
2981 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2982 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2983 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2984 Operand.getNode()->getOperand(0));
2985 if (OpOpcode == ISD::FNEG) // --X -> X
2986 return Operand.getNode()->getOperand(0);
2989 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2990 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2995 SDVTList VTs = getVTList(VT);
2996 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2997 FoldingSetNodeID ID;
2998 SDValue Ops[1] = { Operand };
2999 AddNodeIDNode(ID, Opcode, VTs, Ops);
3001 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3002 return SDValue(E, 0);
3004 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3005 DL.getDebugLoc(), VTs, Operand);
3006 CSEMap.InsertNode(N, IP);
3008 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3009 DL.getDebugLoc(), VTs, Operand);
3013 return SDValue(N, 0);
3016 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3017 SDNode *Cst1, SDNode *Cst2) {
3018 // If the opcode is a target-specific ISD node, there's nothing we can
3019 // do here and the operand rules may not line up with the below, so
3021 if (Opcode >= ISD::BUILTIN_OP_END)
3024 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3025 SmallVector<SDValue, 4> Outputs;
3026 EVT SVT = VT.getScalarType();
3028 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3029 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3030 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3033 if (Scalar1 && Scalar2)
3034 // Scalar instruction.
3035 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3037 // For vectors extract each constant element into Inputs so we can constant
3038 // fold them individually.
3039 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3040 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3044 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3046 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3047 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3048 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3049 if (!V1 || !V2) // Not a constant, bail.
3052 if (V1->isOpaque() || V2->isOpaque())
3055 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3056 // FIXME: This is valid and could be handled by truncating the APInts.
3057 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3060 Inputs.push_back(std::make_pair(V1, V2));
3064 // We have a number of constant values, constant fold them element by element.
3065 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3066 const APInt &C1 = Inputs[I].first->getAPIntValue();
3067 const APInt &C2 = Inputs[I].second->getAPIntValue();
3071 Outputs.push_back(getConstant(C1 + C2, SVT));
3074 Outputs.push_back(getConstant(C1 - C2, SVT));
3077 Outputs.push_back(getConstant(C1 * C2, SVT));
3080 if (!C2.getBoolValue())
3082 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3085 if (!C2.getBoolValue())
3087 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3090 if (!C2.getBoolValue())
3092 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3095 if (!C2.getBoolValue())
3097 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3100 Outputs.push_back(getConstant(C1 & C2, SVT));
3103 Outputs.push_back(getConstant(C1 | C2, SVT));
3106 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3109 Outputs.push_back(getConstant(C1 << C2, SVT));
3112 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3115 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3118 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3121 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3128 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3129 "Expected a scalar or vector!"));
3131 // Handle the scalar case first.
3133 return Outputs.back();
3135 // We may have a vector type but a scalar result. Create a splat.
3136 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3138 // Build a big vector out of the scalar elements we generated.
3139 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3142 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3143 SDValue N2, bool nuw, bool nsw, bool exact) {
3144 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3145 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3148 case ISD::TokenFactor:
3149 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3150 N2.getValueType() == MVT::Other && "Invalid token factor!");
3151 // Fold trivial token factors.
3152 if (N1.getOpcode() == ISD::EntryToken) return N2;
3153 if (N2.getOpcode() == ISD::EntryToken) return N1;
3154 if (N1 == N2) return N1;
3156 case ISD::CONCAT_VECTORS:
3157 // Concat of UNDEFs is UNDEF.
3158 if (N1.getOpcode() == ISD::UNDEF &&
3159 N2.getOpcode() == ISD::UNDEF)
3160 return getUNDEF(VT);
3162 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3163 // one big BUILD_VECTOR.
3164 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3165 N2.getOpcode() == ISD::BUILD_VECTOR) {
3166 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3167 N1.getNode()->op_end());
3168 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3169 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3173 assert(VT.isInteger() && "This operator does not apply to FP types!");
3174 assert(N1.getValueType() == N2.getValueType() &&
3175 N1.getValueType() == VT && "Binary operator types must match!");
3176 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3177 // worth handling here.
3178 if (N2C && N2C->isNullValue())
3180 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3187 assert(VT.isInteger() && "This operator does not apply to FP types!");
3188 assert(N1.getValueType() == N2.getValueType() &&
3189 N1.getValueType() == VT && "Binary operator types must match!");
3190 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3191 // it's worth handling here.
3192 if (N2C && N2C->isNullValue())
3202 assert(VT.isInteger() && "This operator does not apply to FP types!");
3203 assert(N1.getValueType() == N2.getValueType() &&
3204 N1.getValueType() == VT && "Binary operator types must match!");
3211 if (getTarget().Options.UnsafeFPMath) {
3212 if (Opcode == ISD::FADD) {
3214 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3215 if (CFP->getValueAPF().isZero())
3218 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3219 if (CFP->getValueAPF().isZero())
3221 } else if (Opcode == ISD::FSUB) {
3223 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3224 if (CFP->getValueAPF().isZero())
3226 } else if (Opcode == ISD::FMUL) {
3227 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3230 // If the first operand isn't the constant, try the second
3232 CFP = dyn_cast<ConstantFPSDNode>(N2);
3239 return SDValue(CFP,0);
3241 if (CFP->isExactlyValue(1.0))
3246 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3247 assert(N1.getValueType() == N2.getValueType() &&
3248 N1.getValueType() == VT && "Binary operator types must match!");
3250 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3251 assert(N1.getValueType() == VT &&
3252 N1.getValueType().isFloatingPoint() &&
3253 N2.getValueType().isFloatingPoint() &&
3254 "Invalid FCOPYSIGN!");
3261 assert(VT == N1.getValueType() &&
3262 "Shift operators return type must be the same as their first arg");
3263 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3264 "Shifts only work on integers");
3265 assert((!VT.isVector() || VT == N2.getValueType()) &&
3266 "Vector shift amounts must be in the same as their first arg");
3267 // Verify that the shift amount VT is bit enough to hold valid shift
3268 // amounts. This catches things like trying to shift an i1024 value by an
3269 // i8, which is easy to fall into in generic code that uses
3270 // TLI.getShiftAmount().
3271 assert(N2.getValueType().getSizeInBits() >=
3272 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3273 "Invalid use of small shift amount with oversized value!");
3275 // Always fold shifts of i1 values so the code generator doesn't need to
3276 // handle them. Since we know the size of the shift has to be less than the
3277 // size of the value, the shift/rotate count is guaranteed to be zero.
3280 if (N2C && N2C->isNullValue())
3283 case ISD::FP_ROUND_INREG: {
3284 EVT EVT = cast<VTSDNode>(N2)->getVT();
3285 assert(VT == N1.getValueType() && "Not an inreg round!");
3286 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3287 "Cannot FP_ROUND_INREG integer types");
3288 assert(EVT.isVector() == VT.isVector() &&
3289 "FP_ROUND_INREG type should be vector iff the operand "
3291 assert((!EVT.isVector() ||
3292 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3293 "Vector element counts must match in FP_ROUND_INREG");
3294 assert(EVT.bitsLE(VT) && "Not rounding down!");
3296 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3300 assert(VT.isFloatingPoint() &&
3301 N1.getValueType().isFloatingPoint() &&
3302 VT.bitsLE(N1.getValueType()) &&
3303 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3304 if (N1.getValueType() == VT) return N1; // noop conversion.
3306 case ISD::AssertSext:
3307 case ISD::AssertZext: {
3308 EVT EVT = cast<VTSDNode>(N2)->getVT();
3309 assert(VT == N1.getValueType() && "Not an inreg extend!");
3310 assert(VT.isInteger() && EVT.isInteger() &&
3311 "Cannot *_EXTEND_INREG FP types");
3312 assert(!EVT.isVector() &&
3313 "AssertSExt/AssertZExt type should be the vector element type "
3314 "rather than the vector type!");
3315 assert(EVT.bitsLE(VT) && "Not extending!");
3316 if (VT == EVT) return N1; // noop assertion.
3319 case ISD::SIGN_EXTEND_INREG: {
3320 EVT EVT = cast<VTSDNode>(N2)->getVT();
3321 assert(VT == N1.getValueType() && "Not an inreg extend!");
3322 assert(VT.isInteger() && EVT.isInteger() &&
3323 "Cannot *_EXTEND_INREG FP types");
3324 assert(EVT.isVector() == VT.isVector() &&
3325 "SIGN_EXTEND_INREG type should be vector iff the operand "
3327 assert((!EVT.isVector() ||
3328 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3329 "Vector element counts must match in SIGN_EXTEND_INREG");
3330 assert(EVT.bitsLE(VT) && "Not extending!");
3331 if (EVT == VT) return N1; // Not actually extending
3334 APInt Val = N1C->getAPIntValue();
3335 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3336 Val <<= Val.getBitWidth()-FromBits;
3337 Val = Val.ashr(Val.getBitWidth()-FromBits);
3338 return getConstant(Val, VT);
3342 case ISD::EXTRACT_VECTOR_ELT:
3343 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3344 if (N1.getOpcode() == ISD::UNDEF)
3345 return getUNDEF(VT);
3347 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3348 // expanding copies of large vectors from registers.
3350 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3351 N1.getNumOperands() > 0) {
3353 N1.getOperand(0).getValueType().getVectorNumElements();
3354 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3355 N1.getOperand(N2C->getZExtValue() / Factor),
3356 getConstant(N2C->getZExtValue() % Factor,
3357 N2.getValueType()));
3360 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3361 // expanding large vector constants.
3362 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3363 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3365 if (VT != Elt.getValueType())
3366 // If the vector element type is not legal, the BUILD_VECTOR operands
3367 // are promoted and implicitly truncated, and the result implicitly
3368 // extended. Make that explicit here.
3369 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3374 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3375 // operations are lowered to scalars.
3376 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3377 // If the indices are the same, return the inserted element else
3378 // if the indices are known different, extract the element from
3379 // the original vector.
3380 SDValue N1Op2 = N1.getOperand(2);
3381 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3383 if (N1Op2C && N2C) {
3384 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3385 if (VT == N1.getOperand(1).getValueType())
3386 return N1.getOperand(1);
3388 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3391 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3395 case ISD::EXTRACT_ELEMENT:
3396 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3397 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3398 (N1.getValueType().isInteger() == VT.isInteger()) &&
3399 N1.getValueType() != VT &&
3400 "Wrong types for EXTRACT_ELEMENT!");
3402 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3403 // 64-bit integers into 32-bit parts. Instead of building the extract of
3404 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3405 if (N1.getOpcode() == ISD::BUILD_PAIR)
3406 return N1.getOperand(N2C->getZExtValue());
3408 // EXTRACT_ELEMENT of a constant int is also very common.
3409 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3410 unsigned ElementSize = VT.getSizeInBits();
3411 unsigned Shift = ElementSize * N2C->getZExtValue();
3412 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3413 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3416 case ISD::EXTRACT_SUBVECTOR: {
3418 if (VT.isSimple() && N1.getValueType().isSimple()) {
3419 assert(VT.isVector() && N1.getValueType().isVector() &&
3420 "Extract subvector VTs must be a vectors!");
3421 assert(VT.getVectorElementType() ==
3422 N1.getValueType().getVectorElementType() &&
3423 "Extract subvector VTs must have the same element type!");
3424 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3425 "Extract subvector must be from larger vector to smaller vector!");
3427 if (isa<ConstantSDNode>(Index.getNode())) {
3428 assert((VT.getVectorNumElements() +
3429 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3430 <= N1.getValueType().getVectorNumElements())
3431 && "Extract subvector overflow!");
3434 // Trivial extraction.
3435 if (VT.getSimpleVT() == N1.getSimpleValueType())
3442 // Perform trivial constant folding.
3444 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3447 // Canonicalize constant to RHS if commutative.
3448 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3449 std::swap(N1C, N2C);
3453 // Constant fold FP operations.
3454 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3455 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3456 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3458 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3459 // Canonicalize constant to RHS if commutative.
3460 std::swap(N1CFP, N2CFP);
3463 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3464 APFloat::opStatus s;
3467 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3468 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3469 return getConstantFP(V1, VT);
3472 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3473 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3474 return getConstantFP(V1, VT);
3477 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3478 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3479 return getConstantFP(V1, VT);
3482 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3483 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3484 s!=APFloat::opDivByZero)) {
3485 return getConstantFP(V1, VT);
3489 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3490 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3491 s!=APFloat::opDivByZero)) {
3492 return getConstantFP(V1, VT);
3495 case ISD::FCOPYSIGN:
3497 return getConstantFP(V1, VT);
3502 if (Opcode == ISD::FP_ROUND) {
3503 APFloat V = N1CFP->getValueAPF(); // make copy
3505 // This can return overflow, underflow, or inexact; we don't care.
3506 // FIXME need to be more flexible about rounding mode.
3507 (void)V.convert(EVTToAPFloatSemantics(VT),
3508 APFloat::rmNearestTiesToEven, &ignored);
3509 return getConstantFP(V, VT);
3513 // Canonicalize an UNDEF to the RHS, even over a constant.
3514 if (N1.getOpcode() == ISD::UNDEF) {
3515 if (isCommutativeBinOp(Opcode)) {
3519 case ISD::FP_ROUND_INREG:
3520 case ISD::SIGN_EXTEND_INREG:
3526 return N1; // fold op(undef, arg2) -> undef
3534 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3535 // For vectors, we can't easily build an all zero vector, just return
3542 // Fold a bunch of operators when the RHS is undef.
3543 if (N2.getOpcode() == ISD::UNDEF) {
3546 if (N1.getOpcode() == ISD::UNDEF)
3547 // Handle undef ^ undef -> 0 special case. This is a common
3549 return getConstant(0, VT);
3559 return N2; // fold op(arg1, undef) -> undef
3565 if (getTarget().Options.UnsafeFPMath)
3573 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3574 // For vectors, we can't easily build an all zero vector, just return
3579 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3580 // For vectors, we can't easily build an all one vector, just return
3588 // Memoize this node if possible.
3590 SDVTList VTs = getVTList(VT);
3591 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3592 if (VT != MVT::Glue) {
3593 SDValue Ops[] = {N1, N2};
3594 FoldingSetNodeID ID;
3595 AddNodeIDNode(ID, Opcode, VTs, Ops);
3597 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3599 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3600 return SDValue(E, 0);
3602 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3604 CSEMap.InsertNode(N, IP);
3607 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3611 return SDValue(N, 0);
3614 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3615 SDValue N1, SDValue N2, SDValue N3) {
3616 // Perform various simplifications.
3617 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3620 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3621 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3622 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3623 if (N1CFP && N2CFP && N3CFP) {
3624 APFloat V1 = N1CFP->getValueAPF();
3625 const APFloat &V2 = N2CFP->getValueAPF();
3626 const APFloat &V3 = N3CFP->getValueAPF();
3627 APFloat::opStatus s =
3628 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3629 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3630 return getConstantFP(V1, VT);
3634 case ISD::CONCAT_VECTORS:
3635 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3636 // one big BUILD_VECTOR.
3637 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3638 N2.getOpcode() == ISD::BUILD_VECTOR &&
3639 N3.getOpcode() == ISD::BUILD_VECTOR) {
3640 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3641 N1.getNode()->op_end());
3642 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3643 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3644 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3648 // Use FoldSetCC to simplify SETCC's.
3649 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3650 if (Simp.getNode()) return Simp;
3655 if (N1C->getZExtValue())
3656 return N2; // select true, X, Y -> X
3657 return N3; // select false, X, Y -> Y
3660 if (N2 == N3) return N2; // select C, X, X -> X
3662 case ISD::VECTOR_SHUFFLE:
3663 llvm_unreachable("should use getVectorShuffle constructor!");
3664 case ISD::INSERT_SUBVECTOR: {
3666 if (VT.isSimple() && N1.getValueType().isSimple()
3667 && N2.getValueType().isSimple()) {
3668 assert(VT.isVector() && N1.getValueType().isVector() &&
3669 N2.getValueType().isVector() &&
3670 "Insert subvector VTs must be a vectors");
3671 assert(VT == N1.getValueType() &&
3672 "Dest and insert subvector source types must match!");
3673 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3674 "Insert subvector must be from smaller vector to larger vector!");
3675 if (isa<ConstantSDNode>(Index.getNode())) {
3676 assert((N2.getValueType().getVectorNumElements() +
3677 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3678 <= VT.getVectorNumElements())
3679 && "Insert subvector overflow!");
3682 // Trivial insertion.
3683 if (VT.getSimpleVT() == N2.getSimpleValueType())
3689 // Fold bit_convert nodes from a type to themselves.
3690 if (N1.getValueType() == VT)
3695 // Memoize node if it doesn't produce a flag.
3697 SDVTList VTs = getVTList(VT);
3698 if (VT != MVT::Glue) {
3699 SDValue Ops[] = { N1, N2, N3 };
3700 FoldingSetNodeID ID;
3701 AddNodeIDNode(ID, Opcode, VTs, Ops);
3703 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3704 return SDValue(E, 0);
3706 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3707 DL.getDebugLoc(), VTs, N1, N2, N3);
3708 CSEMap.InsertNode(N, IP);
3710 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3711 DL.getDebugLoc(), VTs, N1, N2, N3);
3715 return SDValue(N, 0);
3718 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3719 SDValue N1, SDValue N2, SDValue N3,
3721 SDValue Ops[] = { N1, N2, N3, N4 };
3722 return getNode(Opcode, DL, VT, Ops);
3725 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3726 SDValue N1, SDValue N2, SDValue N3,
3727 SDValue N4, SDValue N5) {
3728 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3729 return getNode(Opcode, DL, VT, Ops);
3732 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3733 /// the incoming stack arguments to be loaded from the stack.
3734 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3735 SmallVector<SDValue, 8> ArgChains;
3737 // Include the original chain at the beginning of the list. When this is
3738 // used by target LowerCall hooks, this helps legalize find the
3739 // CALLSEQ_BEGIN node.
3740 ArgChains.push_back(Chain);
3742 // Add a chain value for each stack argument.
3743 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3744 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3745 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3746 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3747 if (FI->getIndex() < 0)
3748 ArgChains.push_back(SDValue(L, 1));
3750 // Build a tokenfactor for all the chains.
3751 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3754 /// getMemsetValue - Vectorized representation of the memset value
3756 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3758 assert(Value.getOpcode() != ISD::UNDEF);
3760 unsigned NumBits = VT.getScalarType().getSizeInBits();
3761 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3762 assert(C->getAPIntValue().getBitWidth() == 8);
3763 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3765 return DAG.getConstant(Val, VT);
3766 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3769 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3771 // Use a multiplication with 0x010101... to extend the input to the
3773 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3774 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3780 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3781 /// used when a memcpy is turned into a memset when the source is a constant
3783 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3784 const TargetLowering &TLI, StringRef Str) {
3785 // Handle vector with all elements zero.
3788 return DAG.getConstant(0, VT);
3789 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3790 return DAG.getConstantFP(0.0, VT);
3791 else if (VT.isVector()) {
3792 unsigned NumElts = VT.getVectorNumElements();
3793 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3794 return DAG.getNode(ISD::BITCAST, dl, VT,
3795 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3798 llvm_unreachable("Expected type!");
3801 assert(!VT.isVector() && "Can't handle vector type here!");
3802 unsigned NumVTBits = VT.getSizeInBits();
3803 unsigned NumVTBytes = NumVTBits / 8;
3804 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3806 APInt Val(NumVTBits, 0);
3807 if (TLI.isLittleEndian()) {
3808 for (unsigned i = 0; i != NumBytes; ++i)
3809 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3811 for (unsigned i = 0; i != NumBytes; ++i)
3812 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3815 // If the "cost" of materializing the integer immediate is less than the cost
3816 // of a load, then it is cost effective to turn the load into the immediate.
3817 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3818 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3819 return DAG.getConstant(Val, VT);
3820 return SDValue(nullptr, 0);
3823 /// getMemBasePlusOffset - Returns base and offset node for the
3825 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3826 SelectionDAG &DAG) {
3827 EVT VT = Base.getValueType();
3828 return DAG.getNode(ISD::ADD, dl,
3829 VT, Base, DAG.getConstant(Offset, VT));
3832 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3834 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3835 unsigned SrcDelta = 0;
3836 GlobalAddressSDNode *G = nullptr;
3837 if (Src.getOpcode() == ISD::GlobalAddress)
3838 G = cast<GlobalAddressSDNode>(Src);
3839 else if (Src.getOpcode() == ISD::ADD &&
3840 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3841 Src.getOperand(1).getOpcode() == ISD::Constant) {
3842 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3843 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3848 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3851 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3852 /// to replace the memset / memcpy. Return true if the number of memory ops
3853 /// is below the threshold. It returns the types of the sequence of
3854 /// memory ops to perform memset / memcpy by reference.
3855 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3856 unsigned Limit, uint64_t Size,
3857 unsigned DstAlign, unsigned SrcAlign,
3863 const TargetLowering &TLI) {
3864 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3865 "Expecting memcpy / memset source to meet alignment requirement!");
3866 // If 'SrcAlign' is zero, that means the memory operation does not need to
3867 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3868 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3869 // is the specified alignment of the memory operation. If it is zero, that
3870 // means it's possible to change the alignment of the destination.
3871 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3872 // not need to be loaded.
3873 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3874 IsMemset, ZeroMemset, MemcpyStrSrc,
3875 DAG.getMachineFunction());
3877 if (VT == MVT::Other) {
3879 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3880 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3881 VT = TLI.getPointerTy();
3883 switch (DstAlign & 7) {
3884 case 0: VT = MVT::i64; break;
3885 case 4: VT = MVT::i32; break;
3886 case 2: VT = MVT::i16; break;
3887 default: VT = MVT::i8; break;
3892 while (!TLI.isTypeLegal(LVT))
3893 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3894 assert(LVT.isInteger());
3900 unsigned NumMemOps = 0;
3902 unsigned VTSize = VT.getSizeInBits() / 8;
3903 while (VTSize > Size) {
3904 // For now, only use non-vector load / store's for the left-over pieces.
3909 if (VT.isVector() || VT.isFloatingPoint()) {
3910 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3911 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3912 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3914 else if (NewVT == MVT::i64 &&
3915 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3916 TLI.isSafeMemOpType(MVT::f64)) {
3917 // i64 is usually not legal on 32-bit targets, but f64 may be.
3925 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3926 if (NewVT == MVT::i8)
3928 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3930 NewVTSize = NewVT.getSizeInBits() / 8;
3932 // If the new VT cannot cover all of the remaining bits, then consider
3933 // issuing a (or a pair of) unaligned and overlapping load / store.
3934 // FIXME: Only does this for 64-bit or more since we don't have proper
3935 // cost model for unaligned load / store.
3938 if (NumMemOps && AllowOverlap &&
3939 VTSize >= 8 && NewVTSize < Size &&
3940 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3948 if (++NumMemOps > Limit)
3951 MemOps.push_back(VT);
3958 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3959 SDValue Chain, SDValue Dst,
3960 SDValue Src, uint64_t Size,
3961 unsigned Align, bool isVol,
3963 MachinePointerInfo DstPtrInfo,
3964 MachinePointerInfo SrcPtrInfo) {
3965 // Turn a memcpy of undef to nop.
3966 if (Src.getOpcode() == ISD::UNDEF)
3969 // Expand memcpy to a series of load and store ops if the size operand falls
3970 // below a certain threshold.
3971 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3972 // rather than maybe a humongous number of loads and stores.
3973 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3974 std::vector<EVT> MemOps;
3975 bool DstAlignCanChange = false;
3976 MachineFunction &MF = DAG.getMachineFunction();
3977 MachineFrameInfo *MFI = MF.getFrameInfo();
3978 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
3979 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3980 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3981 DstAlignCanChange = true;
3982 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3983 if (Align > SrcAlign)
3986 bool CopyFromStr = isMemSrcFromString(Src, Str);
3987 bool isZeroStr = CopyFromStr && Str.empty();
3988 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3990 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3991 (DstAlignCanChange ? 0 : Align),
3992 (isZeroStr ? 0 : SrcAlign),
3993 false, false, CopyFromStr, true, DAG, TLI))
3996 if (DstAlignCanChange) {
3997 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3998 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4000 // Don't promote to an alignment that would require dynamic stack
4002 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4003 if (!TRI->needsStackRealignment(MF))
4004 while (NewAlign > Align &&
4005 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4008 if (NewAlign > Align) {
4009 // Give the stack frame object a larger alignment if needed.
4010 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4011 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4016 SmallVector<SDValue, 8> OutChains;
4017 unsigned NumMemOps = MemOps.size();
4018 uint64_t SrcOff = 0, DstOff = 0;
4019 for (unsigned i = 0; i != NumMemOps; ++i) {
4021 unsigned VTSize = VT.getSizeInBits() / 8;
4022 SDValue Value, Store;
4024 if (VTSize > Size) {
4025 // Issuing an unaligned load / store pair that overlaps with the previous
4026 // pair. Adjust the offset accordingly.
4027 assert(i == NumMemOps-1 && i != 0);
4028 SrcOff -= VTSize - Size;
4029 DstOff -= VTSize - Size;
4033 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4034 // It's unlikely a store of a vector immediate can be done in a single
4035 // instruction. It would require a load from a constantpool first.
4036 // We only handle zero vectors here.
4037 // FIXME: Handle other cases where store of vector immediate is done in
4038 // a single instruction.
4039 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4040 if (Value.getNode())
4041 Store = DAG.getStore(Chain, dl, Value,
4042 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4043 DstPtrInfo.getWithOffset(DstOff), isVol,
4047 if (!Store.getNode()) {
4048 // The type might not be legal for the target. This should only happen
4049 // if the type is smaller than a legal type, as on PPC, so the right
4050 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4051 // to Load/Store if NVT==VT.
4052 // FIXME does the case above also need this?
4053 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4054 assert(NVT.bitsGE(VT));
4055 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4056 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4057 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4058 false, MinAlign(SrcAlign, SrcOff));
4059 Store = DAG.getTruncStore(Chain, dl, Value,
4060 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4061 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4064 OutChains.push_back(Store);
4070 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4073 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4074 SDValue Chain, SDValue Dst,
4075 SDValue Src, uint64_t Size,
4076 unsigned Align, bool isVol,
4078 MachinePointerInfo DstPtrInfo,
4079 MachinePointerInfo SrcPtrInfo) {
4080 // Turn a memmove of undef to nop.
4081 if (Src.getOpcode() == ISD::UNDEF)
4084 // Expand memmove to a series of load and store ops if the size operand falls
4085 // below a certain threshold.
4086 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4087 std::vector<EVT> MemOps;
4088 bool DstAlignCanChange = false;
4089 MachineFunction &MF = DAG.getMachineFunction();
4090 MachineFrameInfo *MFI = MF.getFrameInfo();
4091 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4092 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4093 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4094 DstAlignCanChange = true;
4095 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4096 if (Align > SrcAlign)
4098 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4100 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4101 (DstAlignCanChange ? 0 : Align), SrcAlign,
4102 false, false, false, false, DAG, TLI))
4105 if (DstAlignCanChange) {
4106 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4107 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4108 if (NewAlign > Align) {
4109 // Give the stack frame object a larger alignment if needed.
4110 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4111 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4116 uint64_t SrcOff = 0, DstOff = 0;
4117 SmallVector<SDValue, 8> LoadValues;
4118 SmallVector<SDValue, 8> LoadChains;
4119 SmallVector<SDValue, 8> OutChains;
4120 unsigned NumMemOps = MemOps.size();
4121 for (unsigned i = 0; i < NumMemOps; i++) {
4123 unsigned VTSize = VT.getSizeInBits() / 8;
4126 Value = DAG.getLoad(VT, dl, Chain,
4127 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4128 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4129 false, false, SrcAlign);
4130 LoadValues.push_back(Value);
4131 LoadChains.push_back(Value.getValue(1));
4134 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4136 for (unsigned i = 0; i < NumMemOps; i++) {
4138 unsigned VTSize = VT.getSizeInBits() / 8;
4141 Store = DAG.getStore(Chain, dl, LoadValues[i],
4142 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4143 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4144 OutChains.push_back(Store);
4148 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4151 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4154 /// \param DAG Selection DAG where lowered code is placed.
4155 /// \param dl Link to corresponding IR location.
4156 /// \param Chain Control flow dependency.
4157 /// \param Dst Pointer to destination memory location.
4158 /// \param Src Value of byte to write into the memory.
4159 /// \param Size Number of bytes to write.
4160 /// \param Align Alignment of the destination in bytes.
4161 /// \param isVol True if destination is volatile.
4162 /// \param DstPtrInfo IR information on the memory pointer.
4163 /// \returns New head in the control flow, if lowering was successful, empty
4164 /// SDValue otherwise.
4166 /// The function tries to replace 'llvm.memset' intrinsic with several store
4167 /// operations and value calculation code. This is usually profitable for small
4169 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4170 SDValue Chain, SDValue Dst,
4171 SDValue Src, uint64_t Size,
4172 unsigned Align, bool isVol,
4173 MachinePointerInfo DstPtrInfo) {
4174 // Turn a memset of undef to nop.
4175 if (Src.getOpcode() == ISD::UNDEF)
4178 // Expand memset to a series of load/store ops if the size operand
4179 // falls below a certain threshold.
4180 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4181 std::vector<EVT> MemOps;
4182 bool DstAlignCanChange = false;
4183 MachineFunction &MF = DAG.getMachineFunction();
4184 MachineFrameInfo *MFI = MF.getFrameInfo();
4185 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4186 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4187 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4188 DstAlignCanChange = true;
4190 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4191 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4192 Size, (DstAlignCanChange ? 0 : Align), 0,
4193 true, IsZeroVal, false, true, DAG, TLI))
4196 if (DstAlignCanChange) {
4197 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4198 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4199 if (NewAlign > Align) {
4200 // Give the stack frame object a larger alignment if needed.
4201 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4202 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4207 SmallVector<SDValue, 8> OutChains;
4208 uint64_t DstOff = 0;
4209 unsigned NumMemOps = MemOps.size();
4211 // Find the largest store and generate the bit pattern for it.
4212 EVT LargestVT = MemOps[0];
4213 for (unsigned i = 1; i < NumMemOps; i++)
4214 if (MemOps[i].bitsGT(LargestVT))
4215 LargestVT = MemOps[i];
4216 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4218 for (unsigned i = 0; i < NumMemOps; i++) {
4220 unsigned VTSize = VT.getSizeInBits() / 8;
4221 if (VTSize > Size) {
4222 // Issuing an unaligned load / store pair that overlaps with the previous
4223 // pair. Adjust the offset accordingly.
4224 assert(i == NumMemOps-1 && i != 0);
4225 DstOff -= VTSize - Size;
4228 // If this store is smaller than the largest store see whether we can get
4229 // the smaller value for free with a truncate.
4230 SDValue Value = MemSetValue;
4231 if (VT.bitsLT(LargestVT)) {
4232 if (!LargestVT.isVector() && !VT.isVector() &&
4233 TLI.isTruncateFree(LargestVT, VT))
4234 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4236 Value = getMemsetValue(Src, VT, DAG, dl);
4238 assert(Value.getValueType() == VT && "Value with wrong type.");
4239 SDValue Store = DAG.getStore(Chain, dl, Value,
4240 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4241 DstPtrInfo.getWithOffset(DstOff),
4242 isVol, false, Align);
4243 OutChains.push_back(Store);
4244 DstOff += VT.getSizeInBits() / 8;
4248 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4251 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4252 SDValue Src, SDValue Size,
4253 unsigned Align, bool isVol, bool AlwaysInline,
4254 MachinePointerInfo DstPtrInfo,
4255 MachinePointerInfo SrcPtrInfo) {
4256 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4258 // Check to see if we should lower the memcpy to loads and stores first.
4259 // For cases within the target-specified limits, this is the best choice.
4260 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4262 // Memcpy with size zero? Just return the original chain.
4263 if (ConstantSize->isNullValue())
4266 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4267 ConstantSize->getZExtValue(),Align,
4268 isVol, false, DstPtrInfo, SrcPtrInfo);
4269 if (Result.getNode())
4273 // Then check to see if we should lower the memcpy with target-specific
4274 // code. If the target chooses to do this, this is the next best.
4276 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4277 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4278 DstPtrInfo, SrcPtrInfo);
4279 if (Result.getNode())
4283 // If we really need inline code and the target declined to provide it,
4284 // use a (potentially long) sequence of loads and stores.
4286 assert(ConstantSize && "AlwaysInline requires a constant size!");
4287 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4288 ConstantSize->getZExtValue(), Align, isVol,
4289 true, DstPtrInfo, SrcPtrInfo);
4292 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4293 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4294 // respect volatile, so they may do things like read or write memory
4295 // beyond the given memory regions. But fixing this isn't easy, and most
4296 // people don't care.
4298 // Emit a library call.
4299 TargetLowering::ArgListTy Args;
4300 TargetLowering::ArgListEntry Entry;
4301 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4302 Entry.Node = Dst; Args.push_back(Entry);
4303 Entry.Node = Src; Args.push_back(Entry);
4304 Entry.Node = Size; Args.push_back(Entry);
4305 // FIXME: pass in SDLoc
4306 TargetLowering::CallLoweringInfo CLI(*this);
4307 CLI.setDebugLoc(dl).setChain(Chain)
4308 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4309 Type::getVoidTy(*getContext()),
4310 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4311 TLI->getPointerTy()), std::move(Args), 0)
4312 .setDiscardResult();
4313 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4315 return CallResult.second;
4318 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4319 SDValue Src, SDValue Size,
4320 unsigned Align, bool isVol,
4321 MachinePointerInfo DstPtrInfo,
4322 MachinePointerInfo SrcPtrInfo) {
4323 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4325 // Check to see if we should lower the memmove to loads and stores first.
4326 // For cases within the target-specified limits, this is the best choice.
4327 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4329 // Memmove with size zero? Just return the original chain.
4330 if (ConstantSize->isNullValue())
4334 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4335 ConstantSize->getZExtValue(), Align, isVol,
4336 false, DstPtrInfo, SrcPtrInfo);
4337 if (Result.getNode())
4341 // Then check to see if we should lower the memmove with target-specific
4342 // code. If the target chooses to do this, this is the next best.
4344 SDValue Result = TSI->EmitTargetCodeForMemmove(
4345 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4346 if (Result.getNode())
4350 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4351 // not be safe. See memcpy above for more details.
4353 // Emit a library call.
4354 TargetLowering::ArgListTy Args;
4355 TargetLowering::ArgListEntry Entry;
4356 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4357 Entry.Node = Dst; Args.push_back(Entry);
4358 Entry.Node = Src; Args.push_back(Entry);
4359 Entry.Node = Size; Args.push_back(Entry);
4360 // FIXME: pass in SDLoc
4361 TargetLowering::CallLoweringInfo CLI(*this);
4362 CLI.setDebugLoc(dl).setChain(Chain)
4363 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4364 Type::getVoidTy(*getContext()),
4365 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4366 TLI->getPointerTy()), std::move(Args), 0)
4367 .setDiscardResult();
4368 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4370 return CallResult.second;
4373 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4374 SDValue Src, SDValue Size,
4375 unsigned Align, bool isVol,
4376 MachinePointerInfo DstPtrInfo) {
4377 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4379 // Check to see if we should lower the memset to stores first.
4380 // For cases within the target-specified limits, this is the best choice.
4381 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4383 // Memset with size zero? Just return the original chain.
4384 if (ConstantSize->isNullValue())
4388 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4389 Align, isVol, DstPtrInfo);
4391 if (Result.getNode())
4395 // Then check to see if we should lower the memset with target-specific
4396 // code. If the target chooses to do this, this is the next best.
4398 SDValue Result = TSI->EmitTargetCodeForMemset(
4399 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4400 if (Result.getNode())
4404 // Emit a library call.
4405 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4406 TargetLowering::ArgListTy Args;
4407 TargetLowering::ArgListEntry Entry;
4408 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4409 Args.push_back(Entry);
4411 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4412 Args.push_back(Entry);
4414 Entry.Ty = IntPtrTy;
4415 Args.push_back(Entry);
4417 // FIXME: pass in SDLoc
4418 TargetLowering::CallLoweringInfo CLI(*this);
4419 CLI.setDebugLoc(dl).setChain(Chain)
4420 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4421 Type::getVoidTy(*getContext()),
4422 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4423 TLI->getPointerTy()), std::move(Args), 0)
4424 .setDiscardResult();
4426 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4427 return CallResult.second;
4430 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4431 SDVTList VTList, ArrayRef<SDValue> Ops,
4432 MachineMemOperand *MMO,
4433 AtomicOrdering SuccessOrdering,
4434 AtomicOrdering FailureOrdering,
4435 SynchronizationScope SynchScope) {
4436 FoldingSetNodeID ID;
4437 ID.AddInteger(MemVT.getRawBits());
4438 AddNodeIDNode(ID, Opcode, VTList, Ops);
4439 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4441 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4442 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4443 return SDValue(E, 0);
4446 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4447 // SDNode doesn't have access to it. This memory will be "leaked" when
4448 // the node is deallocated, but recovered when the allocator is released.
4449 // If the number of operands is less than 5 we use AtomicSDNode's internal
4451 unsigned NumOps = Ops.size();
4452 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4455 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4456 dl.getDebugLoc(), VTList, MemVT,
4457 Ops.data(), DynOps, NumOps, MMO,
4458 SuccessOrdering, FailureOrdering,
4460 CSEMap.InsertNode(N, IP);
4462 return SDValue(N, 0);
4465 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4466 SDVTList VTList, ArrayRef<SDValue> Ops,
4467 MachineMemOperand *MMO,
4468 AtomicOrdering Ordering,
4469 SynchronizationScope SynchScope) {
4470 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4471 Ordering, SynchScope);
4474 SDValue SelectionDAG::getAtomicCmpSwap(
4475 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4476 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4477 unsigned Alignment, AtomicOrdering SuccessOrdering,
4478 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4479 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4480 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4481 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4483 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4484 Alignment = getEVTAlignment(MemVT);
4486 MachineFunction &MF = getMachineFunction();
4488 // FIXME: Volatile isn't really correct; we should keep track of atomic
4489 // orderings in the memoperand.
4490 unsigned Flags = MachineMemOperand::MOVolatile;
4491 Flags |= MachineMemOperand::MOLoad;
4492 Flags |= MachineMemOperand::MOStore;
4494 MachineMemOperand *MMO =
4495 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4497 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4498 SuccessOrdering, FailureOrdering, SynchScope);
4501 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4502 SDVTList VTs, SDValue Chain, SDValue Ptr,
4503 SDValue Cmp, SDValue Swp,
4504 MachineMemOperand *MMO,
4505 AtomicOrdering SuccessOrdering,
4506 AtomicOrdering FailureOrdering,
4507 SynchronizationScope SynchScope) {
4508 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4509 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4510 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4512 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4513 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4514 SuccessOrdering, FailureOrdering, SynchScope);
4517 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4519 SDValue Ptr, SDValue Val,
4520 const Value* PtrVal,
4522 AtomicOrdering Ordering,
4523 SynchronizationScope SynchScope) {
4524 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4525 Alignment = getEVTAlignment(MemVT);
4527 MachineFunction &MF = getMachineFunction();
4528 // An atomic store does not load. An atomic load does not store.
4529 // (An atomicrmw obviously both loads and stores.)
4530 // For now, atomics are considered to be volatile always, and they are
4532 // FIXME: Volatile isn't really correct; we should keep track of atomic
4533 // orderings in the memoperand.
4534 unsigned Flags = MachineMemOperand::MOVolatile;
4535 if (Opcode != ISD::ATOMIC_STORE)
4536 Flags |= MachineMemOperand::MOLoad;
4537 if (Opcode != ISD::ATOMIC_LOAD)
4538 Flags |= MachineMemOperand::MOStore;
4540 MachineMemOperand *MMO =
4541 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4542 MemVT.getStoreSize(), Alignment);
4544 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4545 Ordering, SynchScope);
4548 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4550 SDValue Ptr, SDValue Val,
4551 MachineMemOperand *MMO,
4552 AtomicOrdering Ordering,
4553 SynchronizationScope SynchScope) {
4554 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4555 Opcode == ISD::ATOMIC_LOAD_SUB ||
4556 Opcode == ISD::ATOMIC_LOAD_AND ||
4557 Opcode == ISD::ATOMIC_LOAD_OR ||
4558 Opcode == ISD::ATOMIC_LOAD_XOR ||
4559 Opcode == ISD::ATOMIC_LOAD_NAND ||
4560 Opcode == ISD::ATOMIC_LOAD_MIN ||
4561 Opcode == ISD::ATOMIC_LOAD_MAX ||
4562 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4563 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4564 Opcode == ISD::ATOMIC_SWAP ||
4565 Opcode == ISD::ATOMIC_STORE) &&
4566 "Invalid Atomic Op");
4568 EVT VT = Val.getValueType();
4570 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4571 getVTList(VT, MVT::Other);
4572 SDValue Ops[] = {Chain, Ptr, Val};
4573 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4576 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4577 EVT VT, SDValue Chain,
4579 MachineMemOperand *MMO,
4580 AtomicOrdering Ordering,
4581 SynchronizationScope SynchScope) {
4582 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4584 SDVTList VTs = getVTList(VT, MVT::Other);
4585 SDValue Ops[] = {Chain, Ptr};
4586 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4589 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4590 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4591 if (Ops.size() == 1)
4594 SmallVector<EVT, 4> VTs;
4595 VTs.reserve(Ops.size());
4596 for (unsigned i = 0; i < Ops.size(); ++i)
4597 VTs.push_back(Ops[i].getValueType());
4598 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4602 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4603 ArrayRef<SDValue> Ops,
4604 EVT MemVT, MachinePointerInfo PtrInfo,
4605 unsigned Align, bool Vol,
4606 bool ReadMem, bool WriteMem, unsigned Size) {
4607 if (Align == 0) // Ensure that codegen never sees alignment 0
4608 Align = getEVTAlignment(MemVT);
4610 MachineFunction &MF = getMachineFunction();
4613 Flags |= MachineMemOperand::MOStore;
4615 Flags |= MachineMemOperand::MOLoad;
4617 Flags |= MachineMemOperand::MOVolatile;
4619 Size = MemVT.getStoreSize();
4620 MachineMemOperand *MMO =
4621 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4623 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4627 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4628 ArrayRef<SDValue> Ops, EVT MemVT,
4629 MachineMemOperand *MMO) {
4630 assert((Opcode == ISD::INTRINSIC_VOID ||
4631 Opcode == ISD::INTRINSIC_W_CHAIN ||
4632 Opcode == ISD::PREFETCH ||
4633 Opcode == ISD::LIFETIME_START ||
4634 Opcode == ISD::LIFETIME_END ||
4635 (Opcode <= INT_MAX &&
4636 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4637 "Opcode is not a memory-accessing opcode!");
4639 // Memoize the node unless it returns a flag.
4640 MemIntrinsicSDNode *N;
4641 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4642 FoldingSetNodeID ID;
4643 AddNodeIDNode(ID, Opcode, VTList, Ops);
4644 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4646 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4647 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4648 return SDValue(E, 0);
4651 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4652 dl.getDebugLoc(), VTList, Ops,
4654 CSEMap.InsertNode(N, IP);
4656 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4657 dl.getDebugLoc(), VTList, Ops,
4661 return SDValue(N, 0);
4664 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4665 /// MachinePointerInfo record from it. This is particularly useful because the
4666 /// code generator has many cases where it doesn't bother passing in a
4667 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4668 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4669 // If this is FI+Offset, we can model it.
4670 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4671 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4673 // If this is (FI+Offset1)+Offset2, we can model it.
4674 if (Ptr.getOpcode() != ISD::ADD ||
4675 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4676 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4677 return MachinePointerInfo();
4679 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4680 return MachinePointerInfo::getFixedStack(FI, Offset+
4681 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4684 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4685 /// MachinePointerInfo record from it. This is particularly useful because the
4686 /// code generator has many cases where it doesn't bother passing in a
4687 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4688 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4689 // If the 'Offset' value isn't a constant, we can't handle this.
4690 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4691 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4692 if (OffsetOp.getOpcode() == ISD::UNDEF)
4693 return InferPointerInfo(Ptr);
4694 return MachinePointerInfo();
4699 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4700 EVT VT, SDLoc dl, SDValue Chain,
4701 SDValue Ptr, SDValue Offset,
4702 MachinePointerInfo PtrInfo, EVT MemVT,
4703 bool isVolatile, bool isNonTemporal, bool isInvariant,
4704 unsigned Alignment, const AAMDNodes &AAInfo,
4705 const MDNode *Ranges) {
4706 assert(Chain.getValueType() == MVT::Other &&
4707 "Invalid chain type");
4708 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4709 Alignment = getEVTAlignment(VT);
4711 unsigned Flags = MachineMemOperand::MOLoad;
4713 Flags |= MachineMemOperand::MOVolatile;
4715 Flags |= MachineMemOperand::MONonTemporal;
4717 Flags |= MachineMemOperand::MOInvariant;
4719 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4721 if (PtrInfo.V.isNull())
4722 PtrInfo = InferPointerInfo(Ptr, Offset);
4724 MachineFunction &MF = getMachineFunction();
4725 MachineMemOperand *MMO =
4726 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4728 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4732 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4733 EVT VT, SDLoc dl, SDValue Chain,
4734 SDValue Ptr, SDValue Offset, EVT MemVT,
4735 MachineMemOperand *MMO) {
4737 ExtType = ISD::NON_EXTLOAD;
4738 } else if (ExtType == ISD::NON_EXTLOAD) {
4739 assert(VT == MemVT && "Non-extending load from different memory type!");
4742 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4743 "Should only be an extending load, not truncating!");
4744 assert(VT.isInteger() == MemVT.isInteger() &&
4745 "Cannot convert from FP to Int or Int -> FP!");
4746 assert(VT.isVector() == MemVT.isVector() &&
4747 "Cannot use an ext load to convert to or from a vector!");
4748 assert((!VT.isVector() ||
4749 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4750 "Cannot use an ext load to change the number of vector elements!");
4753 bool Indexed = AM != ISD::UNINDEXED;
4754 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4755 "Unindexed load with an offset!");
4757 SDVTList VTs = Indexed ?
4758 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4759 SDValue Ops[] = { Chain, Ptr, Offset };
4760 FoldingSetNodeID ID;
4761 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4762 ID.AddInteger(MemVT.getRawBits());
4763 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4764 MMO->isNonTemporal(),
4765 MMO->isInvariant()));
4766 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4768 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4769 cast<LoadSDNode>(E)->refineAlignment(MMO);
4770 return SDValue(E, 0);
4772 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4773 dl.getDebugLoc(), VTs, AM, ExtType,
4775 CSEMap.InsertNode(N, IP);
4777 return SDValue(N, 0);
4780 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4781 SDValue Chain, SDValue Ptr,
4782 MachinePointerInfo PtrInfo,
4783 bool isVolatile, bool isNonTemporal,
4784 bool isInvariant, unsigned Alignment,
4785 const AAMDNodes &AAInfo,
4786 const MDNode *Ranges) {
4787 SDValue Undef = getUNDEF(Ptr.getValueType());
4788 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4789 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4793 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4794 SDValue Chain, SDValue Ptr,
4795 MachineMemOperand *MMO) {
4796 SDValue Undef = getUNDEF(Ptr.getValueType());
4797 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4801 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4802 SDValue Chain, SDValue Ptr,
4803 MachinePointerInfo PtrInfo, EVT MemVT,
4804 bool isVolatile, bool isNonTemporal,
4805 bool isInvariant, unsigned Alignment,
4806 const AAMDNodes &AAInfo) {
4807 SDValue Undef = getUNDEF(Ptr.getValueType());
4808 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4809 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4814 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4815 SDValue Chain, SDValue Ptr, EVT MemVT,
4816 MachineMemOperand *MMO) {
4817 SDValue Undef = getUNDEF(Ptr.getValueType());
4818 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4823 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4824 SDValue Offset, ISD::MemIndexedMode AM) {
4825 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4826 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4827 "Load is already a indexed load!");
4828 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4829 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4830 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4831 false, LD->getAlignment());
4834 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4835 SDValue Ptr, MachinePointerInfo PtrInfo,
4836 bool isVolatile, bool isNonTemporal,
4837 unsigned Alignment, const AAMDNodes &AAInfo) {
4838 assert(Chain.getValueType() == MVT::Other &&
4839 "Invalid chain type");
4840 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4841 Alignment = getEVTAlignment(Val.getValueType());
4843 unsigned Flags = MachineMemOperand::MOStore;
4845 Flags |= MachineMemOperand::MOVolatile;
4847 Flags |= MachineMemOperand::MONonTemporal;
4849 if (PtrInfo.V.isNull())
4850 PtrInfo = InferPointerInfo(Ptr);
4852 MachineFunction &MF = getMachineFunction();
4853 MachineMemOperand *MMO =
4854 MF.getMachineMemOperand(PtrInfo, Flags,
4855 Val.getValueType().getStoreSize(), Alignment,
4858 return getStore(Chain, dl, Val, Ptr, MMO);
4861 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4862 SDValue Ptr, MachineMemOperand *MMO) {
4863 assert(Chain.getValueType() == MVT::Other &&
4864 "Invalid chain type");
4865 EVT VT = Val.getValueType();
4866 SDVTList VTs = getVTList(MVT::Other);
4867 SDValue Undef = getUNDEF(Ptr.getValueType());
4868 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4869 FoldingSetNodeID ID;
4870 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4871 ID.AddInteger(VT.getRawBits());
4872 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4873 MMO->isNonTemporal(), MMO->isInvariant()));
4874 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4876 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4877 cast<StoreSDNode>(E)->refineAlignment(MMO);
4878 return SDValue(E, 0);
4880 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4881 dl.getDebugLoc(), VTs,
4882 ISD::UNINDEXED, false, VT, MMO);
4883 CSEMap.InsertNode(N, IP);
4885 return SDValue(N, 0);
4888 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4889 SDValue Ptr, MachinePointerInfo PtrInfo,
4890 EVT SVT,bool isVolatile, bool isNonTemporal,
4892 const AAMDNodes &AAInfo) {
4893 assert(Chain.getValueType() == MVT::Other &&
4894 "Invalid chain type");
4895 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4896 Alignment = getEVTAlignment(SVT);
4898 unsigned Flags = MachineMemOperand::MOStore;
4900 Flags |= MachineMemOperand::MOVolatile;
4902 Flags |= MachineMemOperand::MONonTemporal;
4904 if (PtrInfo.V.isNull())
4905 PtrInfo = InferPointerInfo(Ptr);
4907 MachineFunction &MF = getMachineFunction();
4908 MachineMemOperand *MMO =
4909 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4912 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4915 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4916 SDValue Ptr, EVT SVT,
4917 MachineMemOperand *MMO) {
4918 EVT VT = Val.getValueType();
4920 assert(Chain.getValueType() == MVT::Other &&
4921 "Invalid chain type");
4923 return getStore(Chain, dl, Val, Ptr, MMO);
4925 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4926 "Should only be a truncating store, not extending!");
4927 assert(VT.isInteger() == SVT.isInteger() &&
4928 "Can't do FP-INT conversion!");
4929 assert(VT.isVector() == SVT.isVector() &&
4930 "Cannot use trunc store to convert to or from a vector!");
4931 assert((!VT.isVector() ||
4932 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4933 "Cannot use trunc store to change the number of vector elements!");
4935 SDVTList VTs = getVTList(MVT::Other);
4936 SDValue Undef = getUNDEF(Ptr.getValueType());
4937 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4938 FoldingSetNodeID ID;
4939 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4940 ID.AddInteger(SVT.getRawBits());
4941 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4942 MMO->isNonTemporal(), MMO->isInvariant()));
4943 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4945 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4946 cast<StoreSDNode>(E)->refineAlignment(MMO);
4947 return SDValue(E, 0);
4949 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4950 dl.getDebugLoc(), VTs,
4951 ISD::UNINDEXED, true, SVT, MMO);
4952 CSEMap.InsertNode(N, IP);
4954 return SDValue(N, 0);
4958 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4959 SDValue Offset, ISD::MemIndexedMode AM) {
4960 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4961 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4962 "Store is already a indexed store!");
4963 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4964 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4965 FoldingSetNodeID ID;
4966 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4967 ID.AddInteger(ST->getMemoryVT().getRawBits());
4968 ID.AddInteger(ST->getRawSubclassData());
4969 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4971 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4972 return SDValue(E, 0);
4974 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4975 dl.getDebugLoc(), VTs, AM,
4976 ST->isTruncatingStore(),
4978 ST->getMemOperand());
4979 CSEMap.InsertNode(N, IP);
4981 return SDValue(N, 0);
4985 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
4986 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
4987 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
4989 SDVTList VTs = getVTList(VT, MVT::Other);
4990 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
4991 FoldingSetNodeID ID;
4992 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
4993 ID.AddInteger(VT.getRawBits());
4994 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
4996 MMO->isNonTemporal(),
4997 MMO->isInvariant()));
4998 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5000 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5001 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5002 return SDValue(E, 0);
5004 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5005 dl.getDebugLoc(), Ops, 4, VTs,
5007 CSEMap.InsertNode(N, IP);
5009 return SDValue(N, 0);
5012 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5013 SDValue Ptr, SDValue Mask, EVT MemVT,
5014 MachineMemOperand *MMO, bool isTrunc) {
5015 assert(Chain.getValueType() == MVT::Other &&
5016 "Invalid chain type");
5017 EVT VT = Val.getValueType();
5018 SDVTList VTs = getVTList(MVT::Other);
5019 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5020 FoldingSetNodeID ID;
5021 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5022 ID.AddInteger(VT.getRawBits());
5023 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5024 MMO->isNonTemporal(), MMO->isInvariant()));
5025 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5027 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5028 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5029 return SDValue(E, 0);
5031 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5032 dl.getDebugLoc(), Ops, 4,
5033 VTs, isTrunc, MemVT, MMO);
5034 CSEMap.InsertNode(N, IP);
5036 return SDValue(N, 0);
5039 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5040 SDValue Chain, SDValue Ptr,
5043 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5044 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5047 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5048 ArrayRef<SDUse> Ops) {
5049 switch (Ops.size()) {
5050 case 0: return getNode(Opcode, DL, VT);
5051 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5052 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5053 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5057 // Copy from an SDUse array into an SDValue array for use with
5058 // the regular getNode logic.
5059 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5060 return getNode(Opcode, DL, VT, NewOps);
5063 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5064 ArrayRef<SDValue> Ops) {
5065 unsigned NumOps = Ops.size();
5067 case 0: return getNode(Opcode, DL, VT);
5068 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5069 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5070 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5076 case ISD::SELECT_CC: {
5077 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5078 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5079 "LHS and RHS of condition must have same type!");
5080 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5081 "True and False arms of SelectCC must have same type!");
5082 assert(Ops[2].getValueType() == VT &&
5083 "select_cc node must be of same type as true and false value!");
5087 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5088 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5089 "LHS/RHS of comparison should match types!");
5096 SDVTList VTs = getVTList(VT);
5098 if (VT != MVT::Glue) {
5099 FoldingSetNodeID ID;
5100 AddNodeIDNode(ID, Opcode, VTs, Ops);
5103 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5104 return SDValue(E, 0);
5106 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5108 CSEMap.InsertNode(N, IP);
5110 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5115 return SDValue(N, 0);
5118 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5119 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5120 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5123 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5124 ArrayRef<SDValue> Ops) {
5125 if (VTList.NumVTs == 1)
5126 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5130 // FIXME: figure out how to safely handle things like
5131 // int foo(int x) { return 1 << (x & 255); }
5132 // int bar() { return foo(256); }
5133 case ISD::SRA_PARTS:
5134 case ISD::SRL_PARTS:
5135 case ISD::SHL_PARTS:
5136 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5137 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5138 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5139 else if (N3.getOpcode() == ISD::AND)
5140 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5141 // If the and is only masking out bits that cannot effect the shift,
5142 // eliminate the and.
5143 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5144 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5145 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5151 // Memoize the node unless it returns a flag.
5153 unsigned NumOps = Ops.size();
5154 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5155 FoldingSetNodeID ID;
5156 AddNodeIDNode(ID, Opcode, VTList, Ops);
5158 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5159 return SDValue(E, 0);
5162 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5163 DL.getDebugLoc(), VTList, Ops[0]);
5164 } else if (NumOps == 2) {
5165 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5166 DL.getDebugLoc(), VTList, Ops[0],
5168 } else if (NumOps == 3) {
5169 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5170 DL.getDebugLoc(), VTList, Ops[0],
5173 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5176 CSEMap.InsertNode(N, IP);
5179 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5180 DL.getDebugLoc(), VTList, Ops[0]);
5181 } else if (NumOps == 2) {
5182 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5183 DL.getDebugLoc(), VTList, Ops[0],
5185 } else if (NumOps == 3) {
5186 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5187 DL.getDebugLoc(), VTList, Ops[0],
5190 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5195 return SDValue(N, 0);
5198 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5199 return getNode(Opcode, DL, VTList, None);
5202 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5204 SDValue Ops[] = { N1 };
5205 return getNode(Opcode, DL, VTList, Ops);
5208 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5209 SDValue N1, SDValue N2) {
5210 SDValue Ops[] = { N1, N2 };
5211 return getNode(Opcode, DL, VTList, Ops);
5214 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5215 SDValue N1, SDValue N2, SDValue N3) {
5216 SDValue Ops[] = { N1, N2, N3 };
5217 return getNode(Opcode, DL, VTList, Ops);
5220 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5221 SDValue N1, SDValue N2, SDValue N3,
5223 SDValue Ops[] = { N1, N2, N3, N4 };
5224 return getNode(Opcode, DL, VTList, Ops);
5227 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5228 SDValue N1, SDValue N2, SDValue N3,
5229 SDValue N4, SDValue N5) {
5230 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5231 return getNode(Opcode, DL, VTList, Ops);
5234 SDVTList SelectionDAG::getVTList(EVT VT) {
5235 return makeVTList(SDNode::getValueTypeList(VT), 1);
5238 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5239 FoldingSetNodeID ID;
5241 ID.AddInteger(VT1.getRawBits());
5242 ID.AddInteger(VT2.getRawBits());
5245 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5247 EVT *Array = Allocator.Allocate<EVT>(2);
5250 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5251 VTListMap.InsertNode(Result, IP);
5253 return Result->getSDVTList();
5256 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5257 FoldingSetNodeID ID;
5259 ID.AddInteger(VT1.getRawBits());
5260 ID.AddInteger(VT2.getRawBits());
5261 ID.AddInteger(VT3.getRawBits());
5264 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5266 EVT *Array = Allocator.Allocate<EVT>(3);
5270 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5271 VTListMap.InsertNode(Result, IP);
5273 return Result->getSDVTList();
5276 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5277 FoldingSetNodeID ID;
5279 ID.AddInteger(VT1.getRawBits());
5280 ID.AddInteger(VT2.getRawBits());
5281 ID.AddInteger(VT3.getRawBits());
5282 ID.AddInteger(VT4.getRawBits());
5285 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5287 EVT *Array = Allocator.Allocate<EVT>(4);
5292 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5293 VTListMap.InsertNode(Result, IP);
5295 return Result->getSDVTList();
5298 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5299 unsigned NumVTs = VTs.size();
5300 FoldingSetNodeID ID;
5301 ID.AddInteger(NumVTs);
5302 for (unsigned index = 0; index < NumVTs; index++) {
5303 ID.AddInteger(VTs[index].getRawBits());
5307 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5309 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5310 std::copy(VTs.begin(), VTs.end(), Array);
5311 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5312 VTListMap.InsertNode(Result, IP);
5314 return Result->getSDVTList();
5318 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5319 /// specified operands. If the resultant node already exists in the DAG,
5320 /// this does not modify the specified node, instead it returns the node that
5321 /// already exists. If the resultant node does not exist in the DAG, the
5322 /// input node is returned. As a degenerate case, if you specify the same
5323 /// input operands as the node already has, the input node is returned.
5324 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5325 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5327 // Check to see if there is no change.
5328 if (Op == N->getOperand(0)) return N;
5330 // See if the modified node already exists.
5331 void *InsertPos = nullptr;
5332 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5335 // Nope it doesn't. Remove the node from its current place in the maps.
5337 if (!RemoveNodeFromCSEMaps(N))
5338 InsertPos = nullptr;
5340 // Now we update the operands.
5341 N->OperandList[0].set(Op);
5343 // If this gets put into a CSE map, add it.
5344 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5348 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5349 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5351 // Check to see if there is no change.
5352 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5353 return N; // No operands changed, just return the input node.
5355 // See if the modified node already exists.
5356 void *InsertPos = nullptr;
5357 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5360 // Nope it doesn't. Remove the node from its current place in the maps.
5362 if (!RemoveNodeFromCSEMaps(N))
5363 InsertPos = nullptr;
5365 // Now we update the operands.
5366 if (N->OperandList[0] != Op1)
5367 N->OperandList[0].set(Op1);
5368 if (N->OperandList[1] != Op2)
5369 N->OperandList[1].set(Op2);
5371 // If this gets put into a CSE map, add it.
5372 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5376 SDNode *SelectionDAG::
5377 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5378 SDValue Ops[] = { Op1, Op2, Op3 };
5379 return UpdateNodeOperands(N, Ops);
5382 SDNode *SelectionDAG::
5383 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5384 SDValue Op3, SDValue Op4) {
5385 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5386 return UpdateNodeOperands(N, Ops);
5389 SDNode *SelectionDAG::
5390 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5391 SDValue Op3, SDValue Op4, SDValue Op5) {
5392 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5393 return UpdateNodeOperands(N, Ops);
5396 SDNode *SelectionDAG::
5397 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5398 unsigned NumOps = Ops.size();
5399 assert(N->getNumOperands() == NumOps &&
5400 "Update with wrong number of operands");
5402 // If no operands changed just return the input node.
5403 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5406 // See if the modified node already exists.
5407 void *InsertPos = nullptr;
5408 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5411 // Nope it doesn't. Remove the node from its current place in the maps.
5413 if (!RemoveNodeFromCSEMaps(N))
5414 InsertPos = nullptr;
5416 // Now we update the operands.
5417 for (unsigned i = 0; i != NumOps; ++i)
5418 if (N->OperandList[i] != Ops[i])
5419 N->OperandList[i].set(Ops[i]);
5421 // If this gets put into a CSE map, add it.
5422 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5426 /// DropOperands - Release the operands and set this node to have
5428 void SDNode::DropOperands() {
5429 // Unlike the code in MorphNodeTo that does this, we don't need to
5430 // watch for dead nodes here.
5431 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5437 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5440 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5442 SDVTList VTs = getVTList(VT);
5443 return SelectNodeTo(N, MachineOpc, VTs, None);
5446 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5447 EVT VT, SDValue Op1) {
5448 SDVTList VTs = getVTList(VT);
5449 SDValue Ops[] = { Op1 };
5450 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5453 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5454 EVT VT, SDValue Op1,
5456 SDVTList VTs = getVTList(VT);
5457 SDValue Ops[] = { Op1, Op2 };
5458 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5461 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5462 EVT VT, SDValue Op1,
5463 SDValue Op2, SDValue Op3) {
5464 SDVTList VTs = getVTList(VT);
5465 SDValue Ops[] = { Op1, Op2, Op3 };
5466 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5469 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5470 EVT VT, ArrayRef<SDValue> Ops) {
5471 SDVTList VTs = getVTList(VT);
5472 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5475 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5476 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5477 SDVTList VTs = getVTList(VT1, VT2);
5478 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5481 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5483 SDVTList VTs = getVTList(VT1, VT2);
5484 return SelectNodeTo(N, MachineOpc, VTs, None);
5487 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5488 EVT VT1, EVT VT2, EVT VT3,
5489 ArrayRef<SDValue> Ops) {
5490 SDVTList VTs = getVTList(VT1, VT2, VT3);
5491 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5494 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5495 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5496 ArrayRef<SDValue> Ops) {
5497 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5498 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5501 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5504 SDVTList VTs = getVTList(VT1, VT2);
5505 SDValue Ops[] = { Op1 };
5506 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5509 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5511 SDValue Op1, SDValue Op2) {
5512 SDVTList VTs = getVTList(VT1, VT2);
5513 SDValue Ops[] = { Op1, Op2 };
5514 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5517 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5519 SDValue Op1, SDValue Op2,
5521 SDVTList VTs = getVTList(VT1, VT2);
5522 SDValue Ops[] = { Op1, Op2, Op3 };
5523 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5526 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5527 EVT VT1, EVT VT2, EVT VT3,
5528 SDValue Op1, SDValue Op2,
5530 SDVTList VTs = getVTList(VT1, VT2, VT3);
5531 SDValue Ops[] = { Op1, Op2, Op3 };
5532 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5535 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5536 SDVTList VTs,ArrayRef<SDValue> Ops) {
5537 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5538 // Reset the NodeID to -1.
5543 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5544 /// the line number information on the merged node since it is not possible to
5545 /// preserve the information that operation is associated with multiple lines.
5546 /// This will make the debugger working better at -O0, were there is a higher
5547 /// probability having other instructions associated with that line.
5549 /// For IROrder, we keep the smaller of the two
5550 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5551 DebugLoc NLoc = N->getDebugLoc();
5552 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5553 (OLoc.getDebugLoc() != NLoc)) {
5554 N->setDebugLoc(DebugLoc());
5556 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5557 N->setIROrder(Order);
5561 /// MorphNodeTo - This *mutates* the specified node to have the specified
5562 /// return type, opcode, and operands.
5564 /// Note that MorphNodeTo returns the resultant node. If there is already a
5565 /// node of the specified opcode and operands, it returns that node instead of
5566 /// the current one. Note that the SDLoc need not be the same.
5568 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5569 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5570 /// node, and because it doesn't require CSE recalculation for any of
5571 /// the node's users.
5573 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5574 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5575 /// the legalizer which maintain worklists that would need to be updated when
5576 /// deleting things.
5577 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5578 SDVTList VTs, ArrayRef<SDValue> Ops) {
5579 unsigned NumOps = Ops.size();
5580 // If an identical node already exists, use it.
5582 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5583 FoldingSetNodeID ID;
5584 AddNodeIDNode(ID, Opc, VTs, Ops);
5585 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5586 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5589 if (!RemoveNodeFromCSEMaps(N))
5592 // Start the morphing.
5594 N->ValueList = VTs.VTs;
5595 N->NumValues = VTs.NumVTs;
5597 // Clear the operands list, updating used nodes to remove this from their
5598 // use list. Keep track of any operands that become dead as a result.
5599 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5600 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5602 SDNode *Used = Use.getNode();
5604 if (Used->use_empty())
5605 DeadNodeSet.insert(Used);
5608 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5609 // Initialize the memory references information.
5610 MN->setMemRefs(nullptr, nullptr);
5611 // If NumOps is larger than the # of operands we can have in a
5612 // MachineSDNode, reallocate the operand list.
5613 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5614 if (MN->OperandsNeedDelete)
5615 delete[] MN->OperandList;
5616 if (NumOps > array_lengthof(MN->LocalOperands))
5617 // We're creating a final node that will live unmorphed for the
5618 // remainder of the current SelectionDAG iteration, so we can allocate
5619 // the operands directly out of a pool with no recycling metadata.
5620 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5621 Ops.data(), NumOps);
5623 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5624 MN->OperandsNeedDelete = false;
5626 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5628 // If NumOps is larger than the # of operands we currently have, reallocate
5629 // the operand list.
5630 if (NumOps > N->NumOperands) {
5631 if (N->OperandsNeedDelete)
5632 delete[] N->OperandList;
5633 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5634 N->OperandsNeedDelete = true;
5636 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5639 // Delete any nodes that are still dead after adding the uses for the
5641 if (!DeadNodeSet.empty()) {
5642 SmallVector<SDNode *, 16> DeadNodes;
5643 for (SDNode *N : DeadNodeSet)
5645 DeadNodes.push_back(N);
5646 RemoveDeadNodes(DeadNodes);
5650 CSEMap.InsertNode(N, IP); // Memoize the new node.
5655 /// getMachineNode - These are used for target selectors to create a new node
5656 /// with specified return type(s), MachineInstr opcode, and operands.
5658 /// Note that getMachineNode returns the resultant node. If there is already a
5659 /// node of the specified opcode and operands, it returns that node instead of
5660 /// the current one.
5662 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5663 SDVTList VTs = getVTList(VT);
5664 return getMachineNode(Opcode, dl, VTs, None);
5668 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5669 SDVTList VTs = getVTList(VT);
5670 SDValue Ops[] = { Op1 };
5671 return getMachineNode(Opcode, dl, VTs, Ops);
5675 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5676 SDValue Op1, SDValue Op2) {
5677 SDVTList VTs = getVTList(VT);
5678 SDValue Ops[] = { Op1, Op2 };
5679 return getMachineNode(Opcode, dl, VTs, Ops);
5683 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5684 SDValue Op1, SDValue Op2, SDValue Op3) {
5685 SDVTList VTs = getVTList(VT);
5686 SDValue Ops[] = { Op1, Op2, Op3 };
5687 return getMachineNode(Opcode, dl, VTs, Ops);
5691 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5692 ArrayRef<SDValue> Ops) {
5693 SDVTList VTs = getVTList(VT);
5694 return getMachineNode(Opcode, dl, VTs, Ops);
5698 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5699 SDVTList VTs = getVTList(VT1, VT2);
5700 return getMachineNode(Opcode, dl, VTs, None);
5704 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5705 EVT VT1, EVT VT2, SDValue Op1) {
5706 SDVTList VTs = getVTList(VT1, VT2);
5707 SDValue Ops[] = { Op1 };
5708 return getMachineNode(Opcode, dl, VTs, Ops);
5712 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5713 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5714 SDVTList VTs = getVTList(VT1, VT2);
5715 SDValue Ops[] = { Op1, Op2 };
5716 return getMachineNode(Opcode, dl, VTs, Ops);
5720 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5721 EVT VT1, EVT VT2, SDValue Op1,
5722 SDValue Op2, SDValue Op3) {
5723 SDVTList VTs = getVTList(VT1, VT2);
5724 SDValue Ops[] = { Op1, Op2, Op3 };
5725 return getMachineNode(Opcode, dl, VTs, Ops);
5729 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5731 ArrayRef<SDValue> Ops) {
5732 SDVTList VTs = getVTList(VT1, VT2);
5733 return getMachineNode(Opcode, dl, VTs, Ops);
5737 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5738 EVT VT1, EVT VT2, EVT VT3,
5739 SDValue Op1, SDValue Op2) {
5740 SDVTList VTs = getVTList(VT1, VT2, VT3);
5741 SDValue Ops[] = { Op1, Op2 };
5742 return getMachineNode(Opcode, dl, VTs, Ops);
5746 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5747 EVT VT1, EVT VT2, EVT VT3,
5748 SDValue Op1, SDValue Op2, SDValue Op3) {
5749 SDVTList VTs = getVTList(VT1, VT2, VT3);
5750 SDValue Ops[] = { Op1, Op2, Op3 };
5751 return getMachineNode(Opcode, dl, VTs, Ops);
5755 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5756 EVT VT1, EVT VT2, EVT VT3,
5757 ArrayRef<SDValue> Ops) {
5758 SDVTList VTs = getVTList(VT1, VT2, VT3);
5759 return getMachineNode(Opcode, dl, VTs, Ops);
5763 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5764 EVT VT2, EVT VT3, EVT VT4,
5765 ArrayRef<SDValue> Ops) {
5766 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5767 return getMachineNode(Opcode, dl, VTs, Ops);
5771 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5772 ArrayRef<EVT> ResultTys,
5773 ArrayRef<SDValue> Ops) {
5774 SDVTList VTs = getVTList(ResultTys);
5775 return getMachineNode(Opcode, dl, VTs, Ops);
5779 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5780 ArrayRef<SDValue> OpsArray) {
5781 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5784 const SDValue *Ops = OpsArray.data();
5785 unsigned NumOps = OpsArray.size();
5788 FoldingSetNodeID ID;
5789 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5791 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5792 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5796 // Allocate a new MachineSDNode.
5797 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5798 DL.getDebugLoc(), VTs);
5800 // Initialize the operands list.
5801 if (NumOps > array_lengthof(N->LocalOperands))
5802 // We're creating a final node that will live unmorphed for the
5803 // remainder of the current SelectionDAG iteration, so we can allocate
5804 // the operands directly out of a pool with no recycling metadata.
5805 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5808 N->InitOperands(N->LocalOperands, Ops, NumOps);
5809 N->OperandsNeedDelete = false;
5812 CSEMap.InsertNode(N, IP);
5818 /// getTargetExtractSubreg - A convenience function for creating
5819 /// TargetOpcode::EXTRACT_SUBREG nodes.
5821 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5823 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5824 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5825 VT, Operand, SRIdxVal);
5826 return SDValue(Subreg, 0);
5829 /// getTargetInsertSubreg - A convenience function for creating
5830 /// TargetOpcode::INSERT_SUBREG nodes.
5832 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5833 SDValue Operand, SDValue Subreg) {
5834 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5835 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5836 VT, Operand, Subreg, SRIdxVal);
5837 return SDValue(Result, 0);
5840 /// getNodeIfExists - Get the specified node if it's already available, or
5841 /// else return NULL.
5842 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5843 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5845 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5846 FoldingSetNodeID ID;
5847 AddNodeIDNode(ID, Opcode, VTList, Ops);
5848 if (isBinOpWithFlags(Opcode))
5849 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5851 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5857 /// getDbgValue - Creates a SDDbgValue node.
5860 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5861 unsigned R, bool IsIndirect, uint64_t Off,
5862 DebugLoc DL, unsigned O) {
5863 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5867 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5868 const Value *C, uint64_t Off,
5869 DebugLoc DL, unsigned O) {
5870 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5874 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5875 unsigned FI, uint64_t Off,
5876 DebugLoc DL, unsigned O) {
5877 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5882 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5883 /// pointed to by a use iterator is deleted, increment the use iterator
5884 /// so that it doesn't dangle.
5886 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5887 SDNode::use_iterator &UI;
5888 SDNode::use_iterator &UE;
5890 void NodeDeleted(SDNode *N, SDNode *E) override {
5891 // Increment the iterator as needed.
5892 while (UI != UE && N == *UI)
5897 RAUWUpdateListener(SelectionDAG &d,
5898 SDNode::use_iterator &ui,
5899 SDNode::use_iterator &ue)
5900 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5905 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5906 /// This can cause recursive merging of nodes in the DAG.
5908 /// This version assumes From has a single result value.
5910 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5911 SDNode *From = FromN.getNode();
5912 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5913 "Cannot replace with this method!");
5914 assert(From != To.getNode() && "Cannot replace uses of with self");
5916 // Iterate over all the existing uses of From. New uses will be added
5917 // to the beginning of the use list, which we avoid visiting.
5918 // This specifically avoids visiting uses of From that arise while the
5919 // replacement is happening, because any such uses would be the result
5920 // of CSE: If an existing node looks like From after one of its operands
5921 // is replaced by To, we don't want to replace of all its users with To
5922 // too. See PR3018 for more info.
5923 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5924 RAUWUpdateListener Listener(*this, UI, UE);
5928 // This node is about to morph, remove its old self from the CSE maps.
5929 RemoveNodeFromCSEMaps(User);
5931 // A user can appear in a use list multiple times, and when this
5932 // happens the uses are usually next to each other in the list.
5933 // To help reduce the number of CSE recomputations, process all
5934 // the uses of this user that we can find this way.
5936 SDUse &Use = UI.getUse();
5939 } while (UI != UE && *UI == User);
5941 // Now that we have modified User, add it back to the CSE maps. If it
5942 // already exists there, recursively merge the results together.
5943 AddModifiedNodeToCSEMaps(User);
5946 // If we just RAUW'd the root, take note.
5947 if (FromN == getRoot())
5951 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5952 /// This can cause recursive merging of nodes in the DAG.
5954 /// This version assumes that for each value of From, there is a
5955 /// corresponding value in To in the same position with the same type.
5957 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5959 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5960 assert((!From->hasAnyUseOfValue(i) ||
5961 From->getValueType(i) == To->getValueType(i)) &&
5962 "Cannot use this version of ReplaceAllUsesWith!");
5965 // Handle the trivial case.
5969 // Iterate over just the existing users of From. See the comments in
5970 // the ReplaceAllUsesWith above.
5971 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5972 RAUWUpdateListener Listener(*this, UI, UE);
5976 // This node is about to morph, remove its old self from the CSE maps.
5977 RemoveNodeFromCSEMaps(User);
5979 // A user can appear in a use list multiple times, and when this
5980 // happens the uses are usually next to each other in the list.
5981 // To help reduce the number of CSE recomputations, process all
5982 // the uses of this user that we can find this way.
5984 SDUse &Use = UI.getUse();
5987 } while (UI != UE && *UI == User);
5989 // Now that we have modified User, add it back to the CSE maps. If it
5990 // already exists there, recursively merge the results together.
5991 AddModifiedNodeToCSEMaps(User);
5994 // If we just RAUW'd the root, take note.
5995 if (From == getRoot().getNode())
5996 setRoot(SDValue(To, getRoot().getResNo()));
5999 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6000 /// This can cause recursive merging of nodes in the DAG.
6002 /// This version can replace From with any result values. To must match the
6003 /// number and types of values returned by From.
6004 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6005 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6006 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6008 // Iterate over just the existing users of From. See the comments in
6009 // the ReplaceAllUsesWith above.
6010 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6011 RAUWUpdateListener Listener(*this, UI, UE);
6015 // This node is about to morph, remove its old self from the CSE maps.
6016 RemoveNodeFromCSEMaps(User);
6018 // A user can appear in a use list multiple times, and when this
6019 // happens the uses are usually next to each other in the list.
6020 // To help reduce the number of CSE recomputations, process all
6021 // the uses of this user that we can find this way.
6023 SDUse &Use = UI.getUse();
6024 const SDValue &ToOp = To[Use.getResNo()];
6027 } while (UI != UE && *UI == User);
6029 // Now that we have modified User, add it back to the CSE maps. If it
6030 // already exists there, recursively merge the results together.
6031 AddModifiedNodeToCSEMaps(User);
6034 // If we just RAUW'd the root, take note.
6035 if (From == getRoot().getNode())
6036 setRoot(SDValue(To[getRoot().getResNo()]));
6039 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6040 /// uses of other values produced by From.getNode() alone. The Deleted
6041 /// vector is handled the same way as for ReplaceAllUsesWith.
6042 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6043 // Handle the really simple, really trivial case efficiently.
6044 if (From == To) return;
6046 // Handle the simple, trivial, case efficiently.
6047 if (From.getNode()->getNumValues() == 1) {
6048 ReplaceAllUsesWith(From, To);
6052 // Iterate over just the existing users of From. See the comments in
6053 // the ReplaceAllUsesWith above.
6054 SDNode::use_iterator UI = From.getNode()->use_begin(),
6055 UE = From.getNode()->use_end();
6056 RAUWUpdateListener Listener(*this, UI, UE);
6059 bool UserRemovedFromCSEMaps = false;
6061 // A user can appear in a use list multiple times, and when this
6062 // happens the uses are usually next to each other in the list.
6063 // To help reduce the number of CSE recomputations, process all
6064 // the uses of this user that we can find this way.
6066 SDUse &Use = UI.getUse();
6068 // Skip uses of different values from the same node.
6069 if (Use.getResNo() != From.getResNo()) {
6074 // If this node hasn't been modified yet, it's still in the CSE maps,
6075 // so remove its old self from the CSE maps.
6076 if (!UserRemovedFromCSEMaps) {
6077 RemoveNodeFromCSEMaps(User);
6078 UserRemovedFromCSEMaps = true;
6083 } while (UI != UE && *UI == User);
6085 // We are iterating over all uses of the From node, so if a use
6086 // doesn't use the specific value, no changes are made.
6087 if (!UserRemovedFromCSEMaps)
6090 // Now that we have modified User, add it back to the CSE maps. If it
6091 // already exists there, recursively merge the results together.
6092 AddModifiedNodeToCSEMaps(User);
6095 // If we just RAUW'd the root, take note.
6096 if (From == getRoot())
6101 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6102 /// to record information about a use.
6109 /// operator< - Sort Memos by User.
6110 bool operator<(const UseMemo &L, const UseMemo &R) {
6111 return (intptr_t)L.User < (intptr_t)R.User;
6115 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6116 /// uses of other values produced by From.getNode() alone. The same value
6117 /// may appear in both the From and To list. The Deleted vector is
6118 /// handled the same way as for ReplaceAllUsesWith.
6119 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6122 // Handle the simple, trivial case efficiently.
6124 return ReplaceAllUsesOfValueWith(*From, *To);
6126 // Read up all the uses and make records of them. This helps
6127 // processing new uses that are introduced during the
6128 // replacement process.
6129 SmallVector<UseMemo, 4> Uses;
6130 for (unsigned i = 0; i != Num; ++i) {
6131 unsigned FromResNo = From[i].getResNo();
6132 SDNode *FromNode = From[i].getNode();
6133 for (SDNode::use_iterator UI = FromNode->use_begin(),
6134 E = FromNode->use_end(); UI != E; ++UI) {
6135 SDUse &Use = UI.getUse();
6136 if (Use.getResNo() == FromResNo) {
6137 UseMemo Memo = { *UI, i, &Use };
6138 Uses.push_back(Memo);
6143 // Sort the uses, so that all the uses from a given User are together.
6144 std::sort(Uses.begin(), Uses.end());
6146 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6147 UseIndex != UseIndexEnd; ) {
6148 // We know that this user uses some value of From. If it is the right
6149 // value, update it.
6150 SDNode *User = Uses[UseIndex].User;
6152 // This node is about to morph, remove its old self from the CSE maps.
6153 RemoveNodeFromCSEMaps(User);
6155 // The Uses array is sorted, so all the uses for a given User
6156 // are next to each other in the list.
6157 // To help reduce the number of CSE recomputations, process all
6158 // the uses of this user that we can find this way.
6160 unsigned i = Uses[UseIndex].Index;
6161 SDUse &Use = *Uses[UseIndex].Use;
6165 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6167 // Now that we have modified User, add it back to the CSE maps. If it
6168 // already exists there, recursively merge the results together.
6169 AddModifiedNodeToCSEMaps(User);
6173 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6174 /// based on their topological order. It returns the maximum id and a vector
6175 /// of the SDNodes* in assigned order by reference.
6176 unsigned SelectionDAG::AssignTopologicalOrder() {
6178 unsigned DAGSize = 0;
6180 // SortedPos tracks the progress of the algorithm. Nodes before it are
6181 // sorted, nodes after it are unsorted. When the algorithm completes
6182 // it is at the end of the list.
6183 allnodes_iterator SortedPos = allnodes_begin();
6185 // Visit all the nodes. Move nodes with no operands to the front of
6186 // the list immediately. Annotate nodes that do have operands with their
6187 // operand count. Before we do this, the Node Id fields of the nodes
6188 // may contain arbitrary values. After, the Node Id fields for nodes
6189 // before SortedPos will contain the topological sort index, and the
6190 // Node Id fields for nodes At SortedPos and after will contain the
6191 // count of outstanding operands.
6192 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6194 checkForCycles(N, this);
6195 unsigned Degree = N->getNumOperands();
6197 // A node with no uses, add it to the result array immediately.
6198 N->setNodeId(DAGSize++);
6199 allnodes_iterator Q = N;
6201 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6202 assert(SortedPos != AllNodes.end() && "Overran node list");
6205 // Temporarily use the Node Id as scratch space for the degree count.
6206 N->setNodeId(Degree);
6210 // Visit all the nodes. As we iterate, move nodes into sorted order,
6211 // such that by the time the end is reached all nodes will be sorted.
6212 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6214 checkForCycles(N, this);
6215 // N is in sorted position, so all its uses have one less operand
6216 // that needs to be sorted.
6217 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6220 unsigned Degree = P->getNodeId();
6221 assert(Degree != 0 && "Invalid node degree");
6224 // All of P's operands are sorted, so P may sorted now.
6225 P->setNodeId(DAGSize++);
6227 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6228 assert(SortedPos != AllNodes.end() && "Overran node list");
6231 // Update P's outstanding operand count.
6232 P->setNodeId(Degree);
6235 if (I == SortedPos) {
6238 dbgs() << "Overran sorted position:\n";
6239 S->dumprFull(this); dbgs() << "\n";
6240 dbgs() << "Checking if this is due to cycles\n";
6241 checkForCycles(this, true);
6243 llvm_unreachable(nullptr);
6247 assert(SortedPos == AllNodes.end() &&
6248 "Topological sort incomplete!");
6249 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6250 "First node in topological sort is not the entry token!");
6251 assert(AllNodes.front().getNodeId() == 0 &&
6252 "First node in topological sort has non-zero id!");
6253 assert(AllNodes.front().getNumOperands() == 0 &&
6254 "First node in topological sort has operands!");
6255 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6256 "Last node in topologic sort has unexpected id!");
6257 assert(AllNodes.back().use_empty() &&
6258 "Last node in topologic sort has users!");
6259 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6263 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6264 /// value is produced by SD.
6265 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6267 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6268 SD->setHasDebugValue(true);
6270 DbgInfo->add(DB, SD, isParameter);
6273 /// TransferDbgValues - Transfer SDDbgValues.
6274 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6275 if (From == To || !From.getNode()->getHasDebugValue())
6277 SDNode *FromNode = From.getNode();
6278 SDNode *ToNode = To.getNode();
6279 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6280 SmallVector<SDDbgValue *, 2> ClonedDVs;
6281 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6283 SDDbgValue *Dbg = *I;
6284 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6286 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6287 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6288 Dbg->getDebugLoc(), Dbg->getOrder());
6289 ClonedDVs.push_back(Clone);
6292 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6293 E = ClonedDVs.end(); I != E; ++I)
6294 AddDbgValue(*I, ToNode, false);
6297 //===----------------------------------------------------------------------===//
6299 //===----------------------------------------------------------------------===//
6301 HandleSDNode::~HandleSDNode() {
6305 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6306 DebugLoc DL, const GlobalValue *GA,
6307 EVT VT, int64_t o, unsigned char TF)
6308 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6312 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6313 SDValue X, unsigned SrcAS,
6315 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6316 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6318 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6319 EVT memvt, MachineMemOperand *mmo)
6320 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6321 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6322 MMO->isNonTemporal(), MMO->isInvariant());
6323 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6324 assert(isNonTemporal() == MMO->isNonTemporal() &&
6325 "Non-temporal encoding error!");
6326 // We check here that the size of the memory operand fits within the size of
6327 // the MMO. This is because the MMO might indicate only a possible address
6328 // range instead of specifying the affected memory addresses precisely.
6329 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6332 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6333 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6334 : SDNode(Opc, Order, dl, VTs, Ops),
6335 MemoryVT(memvt), MMO(mmo) {
6336 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6337 MMO->isNonTemporal(), MMO->isInvariant());
6338 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6339 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6342 /// Profile - Gather unique data for the node.
6344 void SDNode::Profile(FoldingSetNodeID &ID) const {
6345 AddNodeIDNode(ID, this);
6350 std::vector<EVT> VTs;
6353 VTs.reserve(MVT::LAST_VALUETYPE);
6354 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6355 VTs.push_back(MVT((MVT::SimpleValueType)i));
6360 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6361 static ManagedStatic<EVTArray> SimpleVTArray;
6362 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6364 /// getValueTypeList - Return a pointer to the specified value type.
6366 const EVT *SDNode::getValueTypeList(EVT VT) {
6367 if (VT.isExtended()) {
6368 sys::SmartScopedLock<true> Lock(*VTMutex);
6369 return &(*EVTs->insert(VT).first);
6371 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6372 "Value type out of range!");
6373 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6377 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6378 /// indicated value. This method ignores uses of other values defined by this
6380 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6381 assert(Value < getNumValues() && "Bad value!");
6383 // TODO: Only iterate over uses of a given value of the node
6384 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6385 if (UI.getUse().getResNo() == Value) {
6392 // Found exactly the right number of uses?
6397 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6398 /// value. This method ignores uses of other values defined by this operation.
6399 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6400 assert(Value < getNumValues() && "Bad value!");
6402 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6403 if (UI.getUse().getResNo() == Value)
6410 /// isOnlyUserOf - Return true if this node is the only use of N.
6412 bool SDNode::isOnlyUserOf(SDNode *N) const {
6414 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6425 /// isOperand - Return true if this node is an operand of N.
6427 bool SDValue::isOperandOf(SDNode *N) const {
6428 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6429 if (*this == N->getOperand(i))
6434 bool SDNode::isOperandOf(SDNode *N) const {
6435 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6436 if (this == N->OperandList[i].getNode())
6441 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6442 /// be a chain) reaches the specified operand without crossing any
6443 /// side-effecting instructions on any chain path. In practice, this looks
6444 /// through token factors and non-volatile loads. In order to remain efficient,
6445 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6446 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6447 unsigned Depth) const {
6448 if (*this == Dest) return true;
6450 // Don't search too deeply, we just want to be able to see through
6451 // TokenFactor's etc.
6452 if (Depth == 0) return false;
6454 // If this is a token factor, all inputs to the TF happen in parallel. If any
6455 // of the operands of the TF does not reach dest, then we cannot do the xform.
6456 if (getOpcode() == ISD::TokenFactor) {
6457 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6458 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6463 // Loads don't have side effects, look through them.
6464 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6465 if (!Ld->isVolatile())
6466 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6471 /// hasPredecessor - Return true if N is a predecessor of this node.
6472 /// N is either an operand of this node, or can be reached by recursively
6473 /// traversing up the operands.
6474 /// NOTE: This is an expensive method. Use it carefully.
6475 bool SDNode::hasPredecessor(const SDNode *N) const {
6476 SmallPtrSet<const SDNode *, 32> Visited;
6477 SmallVector<const SDNode *, 16> Worklist;
6478 return hasPredecessorHelper(N, Visited, Worklist);
6482 SDNode::hasPredecessorHelper(const SDNode *N,
6483 SmallPtrSetImpl<const SDNode *> &Visited,
6484 SmallVectorImpl<const SDNode *> &Worklist) const {
6485 if (Visited.empty()) {
6486 Worklist.push_back(this);
6488 // Take a look in the visited set. If we've already encountered this node
6489 // we needn't search further.
6490 if (Visited.count(N))
6494 // Haven't visited N yet. Continue the search.
6495 while (!Worklist.empty()) {
6496 const SDNode *M = Worklist.pop_back_val();
6497 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6498 SDNode *Op = M->getOperand(i).getNode();
6499 if (Visited.insert(Op).second)
6500 Worklist.push_back(Op);
6509 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6510 assert(Num < NumOperands && "Invalid child # of SDNode!");
6511 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6514 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6515 assert(N->getNumValues() == 1 &&
6516 "Can't unroll a vector with multiple results!");
6518 EVT VT = N->getValueType(0);
6519 unsigned NE = VT.getVectorNumElements();
6520 EVT EltVT = VT.getVectorElementType();
6523 SmallVector<SDValue, 8> Scalars;
6524 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6526 // If ResNE is 0, fully unroll the vector op.
6529 else if (NE > ResNE)
6533 for (i= 0; i != NE; ++i) {
6534 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6535 SDValue Operand = N->getOperand(j);
6536 EVT OperandVT = Operand.getValueType();
6537 if (OperandVT.isVector()) {
6538 // A vector operand; extract a single element.
6539 EVT OperandEltVT = OperandVT.getVectorElementType();
6540 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6543 getConstant(i, TLI->getVectorIdxTy()));
6545 // A scalar operand; just use it as is.
6546 Operands[j] = Operand;
6550 switch (N->getOpcode()) {
6552 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6555 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6562 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6563 getShiftAmountOperand(Operands[0].getValueType(),
6566 case ISD::SIGN_EXTEND_INREG:
6567 case ISD::FP_ROUND_INREG: {
6568 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6569 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6571 getValueType(ExtVT)));
6576 for (; i < ResNE; ++i)
6577 Scalars.push_back(getUNDEF(EltVT));
6579 return getNode(ISD::BUILD_VECTOR, dl,
6580 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6584 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6585 /// location that is 'Dist' units away from the location that the 'Base' load
6586 /// is loading from.
6587 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6588 unsigned Bytes, int Dist) const {
6589 if (LD->getChain() != Base->getChain())
6591 EVT VT = LD->getValueType(0);
6592 if (VT.getSizeInBits() / 8 != Bytes)
6595 SDValue Loc = LD->getOperand(1);
6596 SDValue BaseLoc = Base->getOperand(1);
6597 if (Loc.getOpcode() == ISD::FrameIndex) {
6598 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6600 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6601 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6602 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6603 int FS = MFI->getObjectSize(FI);
6604 int BFS = MFI->getObjectSize(BFI);
6605 if (FS != BFS || FS != (int)Bytes) return false;
6606 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6610 if (isBaseWithConstantOffset(Loc)) {
6611 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6612 if (Loc.getOperand(0) == BaseLoc) {
6613 // If the base location is a simple address with no offset itself, then
6614 // the second load's first add operand should be the base address.
6615 if (LocOffset == Dist * (int)Bytes)
6617 } else if (isBaseWithConstantOffset(BaseLoc)) {
6618 // The base location itself has an offset, so subtract that value from the
6619 // second load's offset before comparing to distance * size.
6621 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6622 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6623 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6628 const GlobalValue *GV1 = nullptr;
6629 const GlobalValue *GV2 = nullptr;
6630 int64_t Offset1 = 0;
6631 int64_t Offset2 = 0;
6632 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6633 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6634 if (isGA1 && isGA2 && GV1 == GV2)
6635 return Offset1 == (Offset2 + Dist*Bytes);
6640 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6641 /// it cannot be inferred.
6642 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6643 // If this is a GlobalAddress + cst, return the alignment.
6644 const GlobalValue *GV;
6645 int64_t GVOffset = 0;
6646 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6647 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6648 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6649 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6650 *TLI->getDataLayout());
6651 unsigned AlignBits = KnownZero.countTrailingOnes();
6652 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6654 return MinAlign(Align, GVOffset);
6657 // If this is a direct reference to a stack slot, use information about the
6658 // stack slot's alignment.
6659 int FrameIdx = 1 << 31;
6660 int64_t FrameOffset = 0;
6661 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6662 FrameIdx = FI->getIndex();
6663 } else if (isBaseWithConstantOffset(Ptr) &&
6664 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6666 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6667 FrameOffset = Ptr.getConstantOperandVal(1);
6670 if (FrameIdx != (1 << 31)) {
6671 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6672 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6680 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6681 /// which is split (or expanded) into two not necessarily identical pieces.
6682 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6683 // Currently all types are split in half.
6685 if (!VT.isVector()) {
6686 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6688 unsigned NumElements = VT.getVectorNumElements();
6689 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6690 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6693 return std::make_pair(LoVT, HiVT);
6696 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6698 std::pair<SDValue, SDValue>
6699 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6701 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6702 N.getValueType().getVectorNumElements() &&
6703 "More vector elements requested than available!");
6705 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6706 getConstant(0, TLI->getVectorIdxTy()));
6707 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6708 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6709 return std::make_pair(Lo, Hi);
6712 void SelectionDAG::ExtractVectorElements(SDValue Op,
6713 SmallVectorImpl<SDValue> &Args,
6714 unsigned Start, unsigned Count) {
6715 EVT VT = Op.getValueType();
6717 Count = VT.getVectorNumElements();
6719 EVT EltVT = VT.getVectorElementType();
6720 EVT IdxTy = TLI->getVectorIdxTy();
6722 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6723 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6724 Op, getConstant(i, IdxTy)));
6728 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6729 unsigned GlobalAddressSDNode::getAddressSpace() const {
6730 return getGlobal()->getType()->getAddressSpace();
6734 Type *ConstantPoolSDNode::getType() const {
6735 if (isMachineConstantPoolEntry())
6736 return Val.MachineCPVal->getType();
6737 return Val.ConstVal->getType();
6740 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6742 unsigned &SplatBitSize,
6744 unsigned MinSplatBits,
6745 bool isBigEndian) const {
6746 EVT VT = getValueType(0);
6747 assert(VT.isVector() && "Expected a vector type");
6748 unsigned sz = VT.getSizeInBits();
6749 if (MinSplatBits > sz)
6752 SplatValue = APInt(sz, 0);
6753 SplatUndef = APInt(sz, 0);
6755 // Get the bits. Bits with undefined values (when the corresponding element
6756 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6757 // in SplatValue. If any of the values are not constant, give up and return
6759 unsigned int nOps = getNumOperands();
6760 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6761 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6763 for (unsigned j = 0; j < nOps; ++j) {
6764 unsigned i = isBigEndian ? nOps-1-j : j;
6765 SDValue OpVal = getOperand(i);
6766 unsigned BitPos = j * EltBitSize;
6768 if (OpVal.getOpcode() == ISD::UNDEF)
6769 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6770 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6771 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6772 zextOrTrunc(sz) << BitPos;
6773 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6774 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6779 // The build_vector is all constants or undefs. Find the smallest element
6780 // size that splats the vector.
6782 HasAnyUndefs = (SplatUndef != 0);
6785 unsigned HalfSize = sz / 2;
6786 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6787 APInt LowValue = SplatValue.trunc(HalfSize);
6788 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6789 APInt LowUndef = SplatUndef.trunc(HalfSize);
6791 // If the two halves do not match (ignoring undef bits), stop here.
6792 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6793 MinSplatBits > HalfSize)
6796 SplatValue = HighValue | LowValue;
6797 SplatUndef = HighUndef & LowUndef;
6806 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6807 if (UndefElements) {
6808 UndefElements->clear();
6809 UndefElements->resize(getNumOperands());
6812 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6813 SDValue Op = getOperand(i);
6814 if (Op.getOpcode() == ISD::UNDEF) {
6816 (*UndefElements)[i] = true;
6817 } else if (!Splatted) {
6819 } else if (Splatted != Op) {
6825 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6826 "Can only have a splat without a constant for all undefs.");
6827 return getOperand(0);
6834 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6835 return dyn_cast_or_null<ConstantSDNode>(
6836 getSplatValue(UndefElements).getNode());
6840 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6841 return dyn_cast_or_null<ConstantFPSDNode>(
6842 getSplatValue(UndefElements).getNode());
6845 bool BuildVectorSDNode::isConstant() const {
6846 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6847 unsigned Opc = getOperand(i).getOpcode();
6848 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6854 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6855 // Find the first non-undef value in the shuffle mask.
6857 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6860 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6862 // Make sure all remaining elements are either undef or the same as the first
6864 for (int Idx = Mask[i]; i != e; ++i)
6865 if (Mask[i] >= 0 && Mask[i] != Idx)
6871 static void checkForCyclesHelper(const SDNode *N,
6872 SmallPtrSetImpl<const SDNode*> &Visited,
6873 SmallPtrSetImpl<const SDNode*> &Checked,
6874 const llvm::SelectionDAG *DAG) {
6875 // If this node has already been checked, don't check it again.
6876 if (Checked.count(N))
6879 // If a node has already been visited on this depth-first walk, reject it as
6881 if (!Visited.insert(N).second) {
6882 errs() << "Detected cycle in SelectionDAG\n";
6883 dbgs() << "Offending node:\n";
6884 N->dumprFull(DAG); dbgs() << "\n";
6888 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6889 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6896 void llvm::checkForCycles(const llvm::SDNode *N,
6897 const llvm::SelectionDAG *DAG,
6905 assert(N && "Checking nonexistent SDNode");
6906 SmallPtrSet<const SDNode*, 32> visited;
6907 SmallPtrSet<const SDNode*, 32> checked;
6908 checkForCyclesHelper(N, visited, checked, DAG);
6913 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6914 checkForCycles(DAG->getRoot().getNode(), DAG, force);